难点:
二分查找的难点在于细节,不等号是否应该带等号
如mid加一还是减一,while到底用<=还是<;
常用使用场景:寻找一个数,寻找左侧边界,寻找右侧边界
注意点:
1. 不要出现else,把所有的情况用else if写清楚
2. “...”标记的地方,是可能出现细节的地方,也是出现坑的地方
3. 为防止left和right过大,计算mid时候残生溢出,计算方式mid = left+(right-left)/2 或者 mid = (left+right)/2,两者计算结果相同
代码如下:
int binarySearch(int[] nums,int target){ int left = 0,right= ... ; while(...){ int mid = left+(right-left)/2; if(nums[mid] == target){ ... }else if(nums[mid] < target){ left = ... }else if(nums[mid] > target){ right = ... } return ...; } }
最基本的二分搜索
题目:704. 二分查找 - 力扣(LeetCode) (leetcode-cn.com)
代码:
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length-1; // 注意点1:right的值 while(left<= right){ // 注意点2: <= int mid = left + (right-left)/2; if(nums[mid] == target){ return mid; }else if(nums[mid]<target){ left = mid+1; //注意点3: mid+1 }else if(nums[mid]>target){ right = mid-1; //注意点4:mid-1 } } return -1; } }
一个要知晓的知识点
对于初始化right的赋值一般有两种情况:
一种是赋值为nums.length-1,即最后一个元素的索引,搜索的空间是[left,right],两端都是封闭空间的;
一种是赋值为nums.length,即数组的长度,搜索的空间是[left,right),因为right=nums.length的索引大小是越界的;
疑问|细节
一、注意点1:在上面基本二分搜索我们使用[left,right],两端都是封闭空间的,即right=nums.length-1;
二、注意点2:为什么在while循环中的条件是<=,不是<?
while中的条件是(循环终止)的条件,也就是说搜索区间为空的应该停止
a.如果while(left<=right),则终止条件是left=right+1,搜索空间就是[right+1,right],可见此时的区间是空的
b.如果while(left<right),则终止条件是left = right,搜索空间是[right,right],此时该区间内非空,还存在可以搜索的空间,如果选择这个条件就会漏掉一种搜索空间case;
如果非要使用这种条件,可以加上我们漏掉的搜索空间;代码如下:
return nums[left] == target ? left:-1;
三、注意点3、4:为什么left=mid+1,right=right-1而不是right=mid,left=mid?
在这里的代码种,我们使用的是两端都封闭的搜索空间[left,right],当我们索引mid发现不是要找的target,下一步的搜索自然是去搜索空间[left,mid-1]或者区间[mid+1,right],因为mid已经搜索过,
应该在接下的搜索空间种删除掉。
四、缺陷:
无法以对数级的复杂度找到target(数组中如果有多个)的左边界和右边界;
ps 如果right=nums.length,此时的搜索区间是左开右闭[left,right),代码修改如下也是正确的
class Solution { public int search(int[] nums, int target) { int left = 0; int right = nums.length; // 注意点1:right的值 while(left< right){ // 注意点2: <= int mid = left + (right-left)/2; if(nums[mid] == target){ return mid; }else if(nums[mid]<target){ left = mid+1; //注意点3: mid+1 }else if(nums[mid]>target){ right = mid; //zhu } } return -1; } }
先看一种普遍的写法:
right初始化为nums.length
代码如下:
int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; // 注意1 while (left < right) { // 注意2 int mid = left + (right - left) / 2; if (nums[mid] == target) { right = mid; //注意3 } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; // 注意4 } } return left; }
疑问|细节
1.注意点2:为什么 while 中是 <
而不是 <=
?
因为right=nums.length,每次循环的搜索区间是[left,right)左闭右开;
while(left<right)终止的条件是left==right,此时的搜索空间[right,right)为空,可以确认终止;
2.为什么没有返回-1的操作,如果nums不存在target的值怎么办?
左侧边界的特殊含义
对于数组[1,2,2,2,3],算法返回1,含义是nums
中小于 2 的元素有 1 个
对于taget=1小于所有数组[2,3,5,7]元素,算法返回0,含义是nums中小于1的元素有0个
对于taget=8大于所有数组[2,3,5,7]元素,算法返回4,含义是nums中小于1的元素有4个
综上得出,函数的返回值(即 left
变量的值)取值区间是闭区间 [0, nums.length]
,所以我们简单添加两行代码就能在正确的时候 return -1:
代码如下:
// target 比所有数都大 if (left == nums.length) return -1; // 类似之前算法的处理方式 return nums[left] == target ? left : -1;
3. 注意点4:为什么 left = mid + 1
,right = mid
?和之前的算法不一样?
「搜索区间」是 [left, right)
左闭右开,所以当 nums[mid]
被检测之后,下一步应该去 mid
的左侧或者右侧区间搜索,即 [left, mid)
或 [mid + 1, right)
4.注意点3:为什么该算法能够搜索左侧边界?
关键在于对于 nums[mid] == target
这种情况的处理:
if (nums[mid] == target) right = mid;
可见,找到 target 时不要立即返回,而是缩小「搜索区间」的上界 right
,在区间 [left, mid)
中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。
5.为什么返回 left
而不是 right
?
while的终止条件是left和right,返回left和right都一样;
6. 怎样right
变成 nums.length - 1
,也就是继续使用两边都闭的「搜索区间」?与第一种二分搜索在某种程度上统一起来了。
可以,代码如下:
int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; //注意点 // 搜索区间为 [left, right] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; //注意点 } else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1] right = mid - 1; //注意点 } else if (nums[mid] == target) { // 收缩右侧边界 right = mid - 1; } } // 检查出界情况 if (left >= nums.length || nums[left] != target) { return -1; } return left; }
类似寻找左侧边界的算法
代码1:
int right_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0, right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { left = mid + 1; // 注意 } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left - 1; // 注意 }
代码2:
int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 这里改成收缩左侧边界即可 left = mid + 1; } } // 这里改为检查 right 越界的情况,见下图 if (right < 0 || nums[right] != target) { return -1; } return right; }