二分查找

最近做题发现之前的二分查找板子还是不对,这次重新梳理二分查找的细节

使用范围:查找的范围是有序的线性表

整数二分查找

 博客转载 

二分查找总结起来就是:思路很简单,细节是魔鬼

这里整理最常用的整数二分查找的场景:寻找一个数、寻找左侧边界、寻找右侧边界

二分查找框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
int left = 0, right = ...; //查找左边界、右边界

while (...) { //判断何时查找终止
int mid = (right + left) / 2; //去中点
if (nums[mid] == target) { //相等时的操作
...
} else if (nums[mid] < target) { //小于时的操作
left = ...
} else if (nums[mid] > target) { //大于时的操作
right = ...
}
}
return ...;
}

分析二分查找的一个技巧是:不要出现 else,而是把所有情况用 else if 写清楚,这样可以清楚地展现所有细节。本文都会使用 else if,旨在讲清楚,读者理解后可自行简化,其中标记的 ... 部分是可能出现细节问题的地方,要着重注意

另外为了防止溢出,求 mid 更好的习惯是 mid=left+(right-left)/2

情况一:基本二分查找

使用场合:在数组中搜索一个数,如果存在返回任意一个索引下标,不存在返回-1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int nums[], int len, int target) {
int left = 0;
int right = len - 1; // 注意查找区间为全闭区间

while (left <= right) { // 注意二分查找终止时为查找区间left>right
int mid = left + (right - left) / 2;
if (nums[mid] == target) //锁定到某个target时返回
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1; //不存在返回-1
}

说明:数组从下标 0 开始,查找区间为全闭区间 [left,right]

问题一:为什么 while 循环的条件中是 <=,而不是 <

因为每次的查找区间都是全闭区间(这是由初始 leftright 取值决定的),如果中途找到了 target 直接返回即可,否则一直找直至查找区间为空的时候也就是 while(left<=right) 时终止循环,这样下一次区间无论如何取值都肯定是 left==rifht+1 了,而当 left==right 时就终止还存在一个元素没有查找

当然如果你非要用 while(left < right) 也可以,我们只需要针对错误原因出现的地方打一个补丁即可:

1
2
3
4
5
//...
while (left < right) {
// ...
}
return nums[left] == target ? left : -1; //再额外判断区间为1的时候

问题二:为什么下次查找区间边界取值是 left=mid+1,right=mid-1,有的写法中是 left=mid+1,right=mid,如何理解区分?

理解的问题一种的查找区间这个概念就好及理解,因为本算法的查找区间的全闭区间,那么当我们发现索引 mid 不是要找的 target 时当然从中去除该判断过的点,所以下次查找区间取 [left,mid-1] 或者 [mid+1,right] 中的一个

问题三:算法有什么缺陷

算法缺陷也是很明显的,如果存在重复的数那么我们找到的那个值可能数值上和 target 相同但是位置是随机的,如果题目想要和 target 数值相同的最左侧的的值或者和 target 数值相同的最右侧的值的索引又如何解决呢?这就需要下面的左侧边界和右侧边界的二分查找了

情况二:查找左侧边界的二分查找

使用场合:在数组中搜索一个数,如果存在返回其索引值最小的下标,不存在返回-1

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int left_bound(int nums[], int len, int target) {
if (len == 0) return -1; //长度为0返回
int left = 0;
int right = len; // 注意查找区间为左闭右开

while (left < right) { // 注意二分查找终止是查找区间为left==right
int mid = left + (right - left) / 2;
if (nums[mid] == target) { //锁定到某个target时不返回而是缩小右边界
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
//return left;
if (left == len) return -1; //target比所有数都大
return nums[left] == target ? left : -1; //类似之前算法的处理方式
}

说明:数组下标从 0 开始,查找区间为左闭右开区间

问题一:为什么 while(left < right) 而不是 <=

用相同的方法分析,因为每次查找区间都是 [left,right) 左闭右开,所以二分查找终止条件 while(left<right) 等价于 left==right,此时查找区间相当于 [left,left) 或者 [right,right),区间恰巧为空也就没必要在相等时继续了

问题二:返回 -1 和返回索引值是怎么判断的?

因为要一步一步来,先理解一下这个「左侧边界」有什么特殊含义:

对于这个数组,算法会返回 1。这个 1 的含义可以这样解读:

  1. 仅适用于数组从下标 0 开始:nums 中小于 2 的元素有 1 个。比如对于有序数组 nums=[2,3,5,7],target = 1,算法会返回 0,含义是:nums 中小于 1 的元素有 0 个。如果 target = 8,算法会返回 4,含义是:nums 中小于 8 的元素有 4 个
  2. 适用于数组从任意下标开始:更深的理解是找到大于等于 target 的第一个元素的下标

综上可以看出,函数的返回值(即 left 变量的值)取值区间是闭区间 [0,len],所以我们简单添加两行代码就能在正确的时候 return -1

  • 如果 left==len 也就是说 target 比数组中任意的数都大返回 -1
  • 如果 nums[left]==target 说明最终缩小的准确的索引值对应的元素就是要找的 target,否则说明 target 在数组的元素数值范围中但是并不存在也返回 -1

考虑一下如果数组是从下标 1 开始那么最终应该如何处理?和上述加黑理解含义一样对判断条件作出相应更改即可

问题三:为什么是 left=mid+1,right=mid?和上述的算法采用的边界取值方法恰好相反了

这也是查找区间开闭性导致的,当 nums[mid] 被检测之后,下一步的查找区间应该去掉 mid 分割成两个区间,即 [left, mid)[mid + 1, right) 其一

问题四:为什么该算法能够查找左侧边界?

原因就在于对 nums[mid]==target 这种情况的处理,算法并没有终止查找返回而是继续缩小查找区间的边界直至查找区间只包含一个元素,可见,找到 target 时不要立即返回,而是缩小查找区间的上界 right,在查找区间 [left, mid) 中继续搜索,即不断向左收缩,达到锁定左侧边界的目的

情况三:查找右侧边界的二分查找

使用场合:在数组中搜索一个数,如果存在返回其索引值最大的下标,不存在返回-1

寻找右侧边界和寻找左侧边界的代码差不多,下次查找区间的划分和上述一样,只有两处不同并标注如下

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int right_bound(int nums[], int len, int target) {
if (len == 0) return -1;
int left = 0, right = len;

while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意锁定到某个target时不返回而是缩小左边界
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
//return left - 1; 注意索引值返回都是找到位置-1
//return right - 1; left和right都行最终两者相等
if (left == 0) return -1; //target比所有数都小
return nums[left - 1] == target ? (left - 1) : -1;
}

说明:数组下标从 0 开始,查找区间为左闭右开区间

问题一:为什么这个算法能够找到右侧边界?

类似地,关键点还是这里:

1
2
if (nums[mid] == target) 
left = mid + 1;

nums[mid] == target 时,不要立即返回,而是增大查找的下界 left,使得区间不断向右收缩,达到锁定右侧边界的目的

问题二:为什么返回索引值用 left 表示而不是用 right

都可以看你心情,因为最终查找区间为空,rightleft 肯定是相等的

问题三:返回 -1 和返回索引值是怎么判断的?为什么找到了要返回的是索引值 -1

前者和上述情况类似

  • 如果 left==0 也就是说 target 比数组中任意的数都小返回 -1
  • 如果 nums[left-1]==target 说明最终缩小的准确的索引值对应的元素就是要找的 target,否则说明 target 在数组的元素数值范围中但是并不存在也返回 -1

后者是因为右侧边界的特殊点导致的,关键在于这个条件的判断:

1
2
if (nums[mid] == target) { // 这样想:mid = left - 1
left = mid + 1;

因为我们对 left 的更新必须是 left=mid+1,就是说 while 循环结束时,nums[left] 一定不等于 target 了,而 nums[left-1] 可能是 target

至于为什么 left 的更新必须是 left=mid+1,同左侧边界搜索,就不再赘述

最终总结

先来梳理一下这些细节差异的因果逻辑:

第一个,最基本的二分查找算法:

1
2
3
4
5
6
7
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

第二个,寻找左侧边界的二分查找:

1
2
3
4
5
6
7
8
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界

第三个,寻找右侧边界的二分查找:

1
2
3
4
5
6
7
8
9
10
11
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid+1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right,必须减一

如果以上内容你都能理解,那么二分查找算法的细节不过如此:只有基本二分查找是全闭区间,边界查找区间的查找就类似 STL 中的 lower_boundupperbound

浮点数二分查找

相比于整数的二分,浮点数的二分好写的多,因为是找区间内一个不确定的大概的数肯定存在,所以它没有取整的问题也不涉及边界是否可取问题(因为肯定是在中间取得)

模板

方法一:以循环次数为循环终止条件

通过控制循环的次数来取得要求精度,60 次循环达到 1e-18 。100 次的循环则可以达到 1e-30 的精度范围,基本上足以解决所有问题

因为有循环限制所以只会出现精度不够,不会出现死循环首推这个写法简单安全

1
2
3
4
5
6
7
8
double bserach(double l,double r,double key){
for(int i=0;i<100;i++){
double mid=(l+r)/2;
if(mid>=key)r=mid;
else l=mid;
}
return (l+r)/2;//最后在取一次确保精度
}

方法二:先定义好终止循环的精度范围

通过限制左右区间相差的距离从而限制 mid 精度

1
2
3
4
5
6
7
8
9
10
#define eps 1e-8

double bserach(double l,double r,double key){
while(r-l>eps){
double mid=(l+r)/2;
if(mid>=key)r=mid;
else l=mid;
}
return (l+r)/2;
}

三分查找

三分查找由浮点数二分查找衍生过来,主要是解决查找凸函数的最值问题

  • 如果 lmrm 在最大(小)值的同一侧: 那么由于单调性,一定是二者中较大(小)的那个离最值近一些,较远的那个点对应的区间不可能包含最值,所以可以舍弃。
  • 如果在两侧: 由于最值在二者中间,我们舍弃两侧的一个区间后,也不会影响最值,所以可以舍弃。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
define eps 1e-8

double val(double x){//带入函数求值
return -2*x*x+5x;
}

double solve(double l,double r){
while(r-l>esp){
double lmid =l+(r-l)/3,rmid=r-(r-l)/3;
if(val(lmid)>=val(rmid))//求极大值
//if(val(lmid) <= val(rmid))求极小值
r = rmid;
else
l = lmid;
}
return val(l);
}