复杂度为O(log n)且有序用二分查找
35-搜索插入位置
思路：二分查找，左右指针 求中间值
注意：while的查询条件是>=
class Solution { public int searchInsert(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]==target){return mid;} if(nums[mid]<target){left=mid+1;} if(nums[mid]>target){right=mid-1;} } return left; } }74-搜索二维矩阵
思路：照常设置左右指针，求出mid ，将mid变成二维数组位置取值，比较大小进行二分查找
注意：while的查询条件是>=；
转换二维数组用/列数 %列数；
class Solution { public boolean searchMatrix(int[][] matrix, int target) { int left=0; int right=matrix.length*matrix[0].length-1; while(left<=right){ int mid=(left+right)/2; int m=mid/matrix[0].length; int n=mid%matrix[0].length; if(matrix[m][n]==target){return true; } if(matrix[m][n]<target){left=mid+1;} if(matrix[m][n]>target){right=mid-1;} } return false; } }34-查找数组相同的所有位置
思路：做两遍二分查找，当nums[mid]==target时多走一步 ，向左走就是求左边界，向右走就是求有边界
注意：最后返回要把两个边界值 拼在一个数组里；
while的查询条件是>=；
设置返回值 初始为-1 ；
class Solution { public int[] searchRange(int[] nums, int target) { int left=0; int right=nums.length-1; int first=findLeft(nums,left,right,target); int last=findRight(nums,left,right,target); return new int[]{first,last};//结果两个存进数组里 } public int findLeft(int[] nums,int left,int right,int target){ int result=-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]==target){result=mid;right=mid-1;}//多走一步 if(nums[mid]>target){right=mid-1;} if(nums[mid]<target){left=mid+1;} } return result; } public int findRight(int[] nums,int left,int right,int target){ int result=-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]==target){result=mid;left=mid+1;}//多走一步 if(nums[mid]>target){right=mid-1;} if(nums[mid]<target){left=mid+1;} } return result; } }33-搜索旋转排序数组
思路：先求一个中点劈开数组，判断 左或右半有序， 再判断target在左半还是右半
注意：if条件里面的< = > ，三种都要考虑 , 不要忘了=，为避免这种问题，尽量用else做剩下；
target判断左半 还是右半， 要在边界用=，而不是在mid上用，因为mid已经判断过了
class Solution { public int search(int[] nums, int target) { int left=0; int right=nums.length-1; while(left<=right){ int mid=(left+right)/2; if(target==nums[mid]){return mid;}//万一直接命中 //判断左半有序 if(nums[left]<=nums[mid]){ //target在左半 if(nums[left]<=target&&target<nums[mid]){right=mid-1;} else{left=mid+1;} } //判断右半有序 else{ //target在右半 if(nums[mid]<target&&target<=nums[right]){left=mid+1;} else{right=mid-1;} } } return -1; } }153-旋转升序数组的最小值
思路：取最小值，用left带回； 取mid劈开，判断最小值在左还是右，就两种情况，要么①在右（移动左边界）， 要么②在左 且 最小值之后升序（移动右边界）； 依次执行只要出现 左高右低 就①，只要出现升序就②
注意：是while的条件没有=，=是终止条件，不然mid=left=right就会死循环；
判断最小值在哪一侧的条件不需要 = ，因为所有的数字都不相同
class Solution { public int findMin(int[] nums) { int left=0; int right=nums.length-1; while(left<right){ int mid=(left+right)/2; if(nums[mid]>nums[right]){ //最小值在右侧 left=mid+1; //用left带回最小值，肯定不是mid }else{//正常升序序列 right=mid; } } return nums[left]; } }
