门面设计装修效果图_会考网页制作视频教程全集_优书网_seo研究中心晴天

六、二分搜索

6.1 简介

给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1
模板四点要素

• 1、初始化
• 2、循环退出条件
• 3、比较中点和目标值
• 4、判断最后两个元素是否符合：A[mid] ==、<、> target
  时间复杂度O(logn)，使用场景一般是有序数组的查找

6.2 典型实例 – 二分查找

704. 二分查找

class Solution {// 二分搜索最常用模板public int search(int[] nums, int target) {// method1: 基于迭代// int left = 0, right = nums.length-1;// while (left<=right){//     int mid = (left+right)/2;//     if(target > nums[mid]){//         left = mid+1;//     }else if(target < nums[mid]){//         right = mid-1;//     }else{//         return mid;//     }// }// return -1;// method2: 基于递归return search(0, nums.length - 1, nums, target);}private int search(int left, int right, int[] nums, int target) {if (left > right) {return -1;}int mid = (left + right) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {return search(left, mid - 1, nums, target);} else {return search(mid + 1, right, nums, target);}}
}

6.2 模板

大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可
另外二分查找还有一些其他模板如下图，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛

所以用模板#3就对了，详细的对比可以这边文章介绍：二分搜索模板
如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁常见题目

6.3 常见题目

6.3.1 搜索插入位置

35. 搜索插入位置

class Solution {public int searchInsert(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left+1<right){int mid = left + (right - left)/2;if(nums[mid] == target){return mid;}else if(nums[mid] > target){right = mid;}else{left = mid;}}// 对最后两个结果进行判断 (此时：left+1=right)// target逻辑上最终的落点：负无穷,left,right,正无穷if(nums[left] >= target){return left;}else if(nums[right] >= target){return right;}else{return right+1;}}
}

6.3.2 搜索二维矩阵

74. 搜索二维矩阵

class Solution {public boolean searchMatrix(int[][] matrix, int target) {// 先定位在哪一行int raw = 0;for(int i = 0;i<matrix.length;i++){if(target >= matrix[i][0] && target <= matrix[i][matrix[i].length-1]){if(target == matrix[i][0] || target == matrix[i][matrix[i].length-1]){return true;}raw = i;break;}}// 在定位中搜索目标值int[] raws = matrix[raw];int left = 0, right = raws.length-1;while(left<=right){int mid = left + (right - left) / 2;if(raws[mid] == target){return true;}else if(raws[mid] > target){right = mid -1;}else{left = mid + 1;}}return false;}
}

6.3.3 寻找旋转排序中数组中的最小值

寻找旋转排序数组中的最小值

class Solution {public int findMin(int[] nums) {if(nums.length == 1){return nums[0];}int left = 0, right = nums.length - 1;while(left + 1 < right){int mid = left + (right - left) / 2;if(nums[mid] < nums[right]){right = mid;}else{left = mid;}}return Math.min(nums[left], nums[right]);}
}

6.3.4 寻找旋转排序数组中的最小值 II

154. 寻找旋转排序数组中的最小值 II

// method1: 若最小值出现不止一次，此方法定位的最小值位置不能确定是否是原单调递增的最左侧的数据位置
class Solution {public int findMin(int[] nums) {if(nums.length == 1){return nums[0];}int left = 0, right = nums.length - 1;while(left + 1 < right){int mid = left + (right - left) / 2;if(nums[mid] < nums[right]){right = mid;}else if(nums[mid] > nums[right]){left = mid;}else{right--;}}return Math.min(nums[left], nums[right]);}
}

// method2: 若最小值出现不止一次，此方法定位的最小值位置是原单调递增的最左侧的数据位置
class Solution {public int findMin(int[] nums) {if(nums.length == 1){return nums[0];}int left = 0, right = nums.length - 1;while(left + 1 < right){while(left<right && nums[left] == nums[left+1]){ // 去除左侧重复数字(仅保留一个)left++;}while(left<right && nums[right] == nums[right-1]){ // 去除右侧重复数字(仅保留一个)right--;}int mid = left + (right - left) / 2;if(nums[mid] < nums[right]){right = mid;}else if(nums[mid] > nums[right]){left = mid;}}return Math.min(nums[left], nums[right]);}
}

6.3.5 搜索旋转排序数组

33.搜索旋转排序数组

// method1: 基于两趟搜索
// 时间复杂度 O(logn)
class Solution {public int search(int[] nums, int target) {if(nums.length == 1){return nums[0]==target?0:-1;}// 找到最小值所在位置// 其左侧（若存在）是递增的// 其右侧（包括它自己）是递增的int left = 0, right = nums.length - 1;while(right - left > 1){int mid = left + (right - left) / 2;if(nums[mid] < nums[right]){right = mid;}else{left = mid;}}// 定位最小值的位置int minIndex = nums[left] < nums[right] ? left:right;// target 可能存在于右边if(target>=nums[minIndex] && target<=nums[nums.length-1]){return search(nums, minIndex, nums.length-1,target);}// target 可能存在于左边（注意：nums本身为递增数组）if(minIndex != 0 && (target>=nums[0] && target<=nums[minIndex-1])){return search(nums, 0, minIndex-1,target);}return -1;}private int search(int[] nums,int left, int right, int target){if(right < 0){return -1;}while(left+1<right){int mid = left + (right-left) / 2;if(nums[mid] == target){return mid;}else if(nums[mid] < target){left = mid;}else{right = mid;}}if(nums[left] == target){return left;}else if(nums[right] == target){return right;}return -1;}
}

// method2: 基于一趟搜索
// 时间复杂度 O(logn)
class Solution {public int search(int[] nums, int target) {if(nums.length == 1){return nums[0]==target?0:-1;}int left = 0, right = nums.length - 1;while(right - left > 1){int mid = left + (right - left) / 2;if(nums[mid] == target){return mid;}if(nums[mid] > nums[left]){ // 位于左边较大的单调区间if(target >= nums[left] && target < nums[mid]){right = mid; // 位于闭区间 [left, mid]}else{ // 位于开区间 [-无穷, left] or [mid, 当前区间的右边界] == [mid, right]// 注意[-无穷, left]就是其右侧的较小单调区间left = mid;}}if(nums[mid] < nums[right]){ // 位于右边较小的单调区间if(target > nums[mid] && target <= nums[right]){left = mid; // 位于闭区间 [mid, right]}else{ // 位于开区间 [当前区间的左边界, mid] or [right, +无穷] == [left, mid]// 注意[right, +无穷]就是其左侧的较大单调区间right = mid;}}}// 对最后的两个数据进行判断if(nums[left] == target){return left;}else if(nums[right] == target){return right;}return -1;}}

6.3.6 搜索旋转排序数组 II

搜索旋转排序数组 II

// mthod1: 基于两趟搜索
// 时间复杂度：O(logn)
class Solution {public boolean search(int[] nums, int target) {// step 1: 定位最小值位置(需要定位原单调递增的最左侧的值的位置)int left = 0, right = nums.length - 1;while(right - left > 1){while(left < right && nums[left] == nums[left+1]){ // 去除左侧重复的数字left++;}while(left < right && nums[right] == nums[right-1]){ // 去除右侧重复的数字right--;}int mid = left + (right - left) / 2;if(nums[mid] < nums[right]){right = mid;}else{left = mid;}}int minIndex = (nums[left] <= nums[right] ? left:right);// step: 判断目标值位于哪个区间中查询if(target>=nums[minIndex] && target <= nums[nums.length - 1]){return search(nums, minIndex, nums.length - 1, target);}if(minIndex !=0 && target >= nums[0] && target <= nums[minIndex-1]){return search(nums, 0, minIndex - 1, target);}return false;}private boolean search(int[] nums, int left, int right, int target){while(right - left > 1){int mid = left + (right - left) / 2;if(nums[mid] == target){return true;}else if(nums[mid] < target){left = mid;}else{right = mid;}}if(nums[left] == target || nums[right] == target){return true;}return false;}
}

// mthod2: 基于一趟搜索
// 时间复杂度：O(logn)
class Solution {public boolean search(int[] nums, int target) {if(nums.length == 1){return nums[0] == target;}int left = 0, right = nums.length - 1;while(right - left > 1){while(left<right && nums[left] == nums[left+1]){left++;}while(left<right && nums[right] == nums[right-1]){right--;}int mid = left + (right - left) / 2;if(nums[mid] == target){return true;}// 当前mid位于左侧区间if(nums[mid] > nums[left]){if(target>=nums[left] && target < nums[mid]){right = mid;}else{left = mid;}}// 当前mid位于右侧区间if(nums[mid] < nums[right]){if(target > nums[mid] && target <= nums[right]){left = mid;}else{right = mid;}}}if(nums[left] == target || nums[right] == target){return true;}return false;}
}

总结

二分搜索四点要素（必背&理解）

• 1、初始化：start=0、end=len-1
• 2、循环退出条件：start + 1 < end
• 3、 比较中间点和目标值：A[mid] ==、<、> target
• 4、判断最后两个元素是否符合：A[start]、A[end] ? target