1.搜索二维矩阵原题链接注意要求代码的时间复杂度为 O(log(m * n))对于整体的数组进行二分查找在定位到数组中的位置publicbooleansearchMatrix(int[][]matrix,inttarget){intmmatrix.length;intnmatrix[0].length;intleft0;intrightm*n-1;while(leftright){intmidleft(right-left)/2;if(matrix[mid/n][mid%n]target){returntrue;}if(matrix[mid/n][mid%n]target){leftmid1;}else{rightmid-1;}}returnfalse;}2.在排序数组中查找元素的第一个和最后一个位置原题链接题目要求时间复杂度是 O(log n)进行两次二分查找寻找两个边界第一次二分找最左边的 target第二次二分找最右边的 targetpublicint[]searchRange(int[]nums,inttarget){intstartfindStart(nums,target);intendfindEnd(nums,target);returnnewint[]{start,end};}//寻找左端点privateintfindStart(int[]nums,inttarget){intans-1;intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){ansmid;rightmid-1;}if(nums[mid]target){leftmid1;}if(nums[mid]target){rightmid-1;}}returnans;}//寻找右端点privateintfindEnd(int[]nums,inttarget){intans-1;intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){ansmid;leftmid1;}if(nums[mid]target){leftmid1;}if(nums[mid]target){rightmid-1;}}returnans;}简化后的代码publicint[]searchRange(int[]nums,inttarget){intfirstlowerBound(nums,target);// 没找到 targetif(firstnums.length||nums[first]!target){returnnewint[]{-1,-1};}intlastlowerBound(nums,target1)-1;returnnewint[]{first,last};}// 找第一个 target 的位置privateintlowerBound(int[]nums,inttarget){intleft0;intrightnums.length;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){rightmid;}else{leftmid1;}}returnleft;}3.搜索旋转排序数组⭐原题链接每次通过 mid 进行二分查找的时候得到的结果要么 [左半部分有序][右半部分无序] 或者 [左半部分无序][右半部分有序]nums 中的每个值都 独一无二因此不存在重叠范围的问题可以通过 left、mid、right 的值判断左右有序的数组如果 target 在有序数组中则直接二分查找否则在递归进行判断下标0123456数组[4,5,6,7,0,1,2]↑ midpublicintsearch(int[]nums,inttarget){intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){returnmid;}//判断是否左有序if(nums[left]nums[mid]){//判断target是否在左有序区间if(targetnums[left]targetnums[mid]){rightmid-1;}else{leftmid1;}}else{//判断target是否在右有序区间if(targetnums[mid]targetnums[right]){leftmid1;}else{rightmid-1;}}}return-1;}4.寻找旋转排序数组中的最小值原题链接最小值其实就是两个有序部分的分界点。同样二分查找中min将数组分为左右两侧左有序右无序或左五序右有序无序的一侧则继续递归publicintfindMin(int[]nums){intleft0;intrightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]nums[right]){// 最小值一定在 mid 右边leftmid1;}else{// 最小值可能是 mid也可能在 mid 左边rightmid;}}returnnums[left];}