二分查找
最近做题发现之前的二分查找板子还是不对,这次重新梳理二分查找的细节
使用范围:查找的范围是有序的线性表
整数二分查找
二分查找总结起来就是:思路很简单,细节是魔鬼
这里整理最常用的整数二分查找的场景:寻找一个数、寻找左侧边界、寻找右侧边界
二分查找框架
1 | int binarySearch(int[] nums, int target) { |
分析二分查找的一个技巧是:不要出现 else,而是把所有情况用 else if 写清楚,这样可以清楚地展现所有细节。本文都会使用 else if,旨在讲清楚,读者理解后可自行简化,其中标记的 ...
部分是可能出现细节问题的地方,要着重注意
另外为了防止溢出,求 mid
更好的习惯是 mid=left+(right-left)/2
情况一:基本二分查找
使用场合:在数组中搜索一个数,如果存在返回任意一个索引下标,不存在返回-1
模板
1 | int binarySearch(int nums[], int len, int target) { |
说明:数组从下标 0 开始,查找区间为全闭区间 [left,right]
问题一:为什么 while
循环的条件中是 <=
,而不是 <
?
因为每次的查找区间都是全闭区间(这是由初始 left
和 right
取值决定的),如果中途找到了 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 | int left_bound(int nums[], int len, int target) { |
说明:数组下标从 0 开始,查找区间为左闭右开区间
问题一:为什么 while(left < right)
而不是 <=
?
用相同的方法分析,因为每次查找区间都是 [left,right)
左闭右开,所以二分查找终止条件 while(left<right)
等价于 left==right
,此时查找区间相当于 [left,left)
或者 [right,right)
,区间恰巧为空也就没必要在相等时继续了
问题二:返回 -1 和返回索引值是怎么判断的?
因为要一步一步来,先理解一下这个「左侧边界」有什么特殊含义:
对于这个数组,算法会返回 1。这个 1 的含义可以这样解读:
- 仅适用于数组从下标 0 开始:nums 中小于 2 的元素有 1 个。比如对于有序数组
nums=[2,3,5,7],target = 1
,算法会返回 0,含义是:nums 中小于 1 的元素有 0 个。如果target = 8
,算法会返回 4,含义是:nums 中小于 8 的元素有 4 个 - 适用于数组从任意下标开始:更深的理解是找到大于等于
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 | int right_bound(int nums[], int len, int target) { |
说明:数组下标从 0 开始,查找区间为左闭右开区间
问题一:为什么这个算法能够找到右侧边界?
类似地,关键点还是这里:
1 | if (nums[mid] == target) |
当 nums[mid] == target
时,不要立即返回,而是增大查找的下界 left
,使得区间不断向右收缩,达到锁定右侧边界的目的
问题二:为什么返回索引值用 left
表示而不是用 right
?
都可以看你心情,因为最终查找区间为空,right
和 left
肯定是相等的
问题三:返回 -1 和返回索引值是怎么判断的?为什么找到了要返回的是索引值 -1
前者和上述情况类似
- 如果
left==0
也就是说target
比数组中任意的数都小返回 -1 - 如果
nums[left-1]==target
说明最终缩小的准确的索引值对应的元素就是要找的target
,否则说明target
在数组的元素数值范围中但是并不存在也返回 -1
后者是因为右侧边界的特殊点导致的,关键在于这个条件的判断:
1 | if (nums[mid] == target) { // 这样想:mid = left - 1 |
因为我们对 left
的更新必须是 left=mid+1
,就是说 while 循环结束时,nums[left]
一定不等于 target
了,而 nums[left-1]
可能是 target
至于为什么 left
的更新必须是 left=mid+1
,同左侧边界搜索,就不再赘述
最终总结
先来梳理一下这些细节差异的因果逻辑:
第一个,最基本的二分查找算法:
1 | 因为我们初始化 right = nums.length - 1 |
第二个,寻找左侧边界的二分查找:
1 | 因为我们初始化 right = nums.length |
第三个,寻找右侧边界的二分查找:
1 | 因为我们初始化 right = nums.length |
如果以上内容你都能理解,那么二分查找算法的细节不过如此:只有基本二分查找是全闭区间,边界查找区间的查找就类似 STL 中的 lower_bound
和 upperbound
浮点数二分查找
相比于整数的二分,浮点数的二分好写的多,因为是找区间内一个不确定的大概的数肯定存在,所以它没有取整的问题也不涉及边界是否可取问题(因为肯定是在中间取得)
模板
方法一:以循环次数为循环终止条件
通过控制循环的次数来取得要求精度,60 次循环达到 1e-18 。100 次的循环则可以达到 1e-30 的精度范围,基本上足以解决所有问题
因为有循环限制所以只会出现精度不够,不会出现死循环首推这个写法简单安全
1 | double bserach(double l,double r,double key){ |
方法二:先定义好终止循环的精度范围
通过限制左右区间相差的距离从而限制
mid
精度
1 |
|
三分查找
三分查找由浮点数二分查找衍生过来,主要是解决查找凸函数的最值问题
- 如果
lm
和rm
在最大(小)值的同一侧: 那么由于单调性,一定是二者中较大(小)的那个离最值近一些,较远的那个点对应的区间不可能包含最值,所以可以舍弃。 - 如果在两侧: 由于最值在二者中间,我们舍弃两侧的一个区间后,也不会影响最值,所以可以舍弃。
1 | define eps 1e-8 |