【LeetCode 手撕算法】（二分查找）搜索插入位置、搜索二维矩阵、查找数组相同的所有位置、搜索旋转排序数组、旋转升序数组的最小值

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