二分查找 - BinarySearch
详细原文这里:特别好用的二分查找法模板
1. 二分查找的基本思想
二分查找的基本思想是:夹逼法
或者叫排除法
在每一轮循环中,都可以排除候选区间里将近一半的元素,进而使得候选区间越来越小,直至有限个数(通常为1个),而这个数就有可能是我们要找的数(在一些情况下,还需要单独做判断)。
2. 编码的细节
- 思考左右边界,如果左右边界不能包括目标数值,二分查找法是怎么都写不对的;
- 先写逻辑上容易想到的分支逻辑,这个分支逻辑通常是排除中位数的逻辑;
- 只写两个分支,一个分支排除中位数,另一个分支不排除中位数;
- 根据分支的逻辑选择中位数的类型,可能是左中位数,也可能是右中位数,标准是避免出现死循环;
- 退出循环的时候,可能需要对
夹逼法
剩下的那个数做一次判断,这一步叫做后处理
3. 细节思考
- 参考代码 1:重点理解为什么候选区间的索引范围是
[0, size]
。
1 | from typing import List |
- 参考代码 2:对于是否接在原有序数组后面单独判断,不满足的时候再在候选区间的索引范围
[0, size-1]
内使用二分查找法进行搜索。
1 | from typing import List |
4. 技巧&调试方法&注意事项
先来看
int mid = left + (right - left) / 2
, 其中left
和right
都是可以取到的数组index- 当
left
和right
是很大的整数的时候,如果写int mid = (left + right) / 2
; 这里left + right
的值就有可能超过int
类型能表示的最大值, 因此使用mid = left + (right - left) // 2
可以避免这种情况。 - 事实上,
mid = left + (right - left) // 2
在right
很大、left
是负数且很小的时候,right - left
也有可能超过int
类型能表示的最大值, 只不过一般情况下left
和right
表示的是数组索引值,left
是非负数,因此right - left
溢出的可能性很小。 - 建议在Java中用
(left + right) >>> 1
,在Python中用(left + right) >> 1
,都是无符号右移。
- 当
当数组的元素个数是偶数的时候,中位数有左中位数和右中位数之分:
- 当数组的元素个数是偶数的时候:
- 使用
mid = left + (right - left) // 2
得到左中位数的索引; - 使用
mid = left + (right - left + 1) // 2
得到右中位数的索引。
- 使用
- 当数组的元素个数是奇数的时候,以上二者都能选到最中间的那个中位数。
- 当数组的元素个数是偶数的时候:
编写分支逻辑的时候,先写 “排除逻辑” 所在的分支。
- 先考虑能把 “中位数” 排除在外的逻辑,而不能排除 “中位数” 的逻辑放在
else
分支里,这样做的理由有 2点:- 可以排除 “中位数” 的逻辑,通常比较好想,但并不绝对,这一点视情况而定
- 分支条数变成 2 条,比原来 3 个分支要考虑的情况少,好处是: 不用在每次循环开始单独考虑中位数是否是目标元素,节约了时间,我们只要在退出循环的时候,即左右区间压缩成一个数(索引)的时候,去判断这个索引表示的数是否是目标元素,而不必在二分的逻辑中单独做判断。
- 先考虑能把 “中位数” 排除在外的逻辑,而不能排除 “中位数” 的逻辑放在
根据分支编写的情况,选择使用左中位数还是右中位数
- 先写判断分支,根据分支的逻辑选中位数,选左中位数还是右中位数,这要做的理由是为了防止出现死循环。死循环容易发生在区间只有 2 个元素时候,此时中位数的选择尤为关键。
- 当出现死循环的时候的调试方法:打印输出左右边界、中位数的值和目标值、分支逻辑等必要的信息
5. 使用总结
- 无脑地写
while left < right:
,这样你就不用判断,在退出循环的时候你应该返回left
还是right
,因为返回left
或者right
都对; - 先写分支逻辑,并且先写排除中位数的逻辑分支(因为更多时候排除中位数的逻辑容易想),另一个分支的逻辑你就不用想了,写出第1个分支的反面代码即可,再根据分支的情况选择使用左中位数还是右中位数;左右分支的规律就如下两点:
- 如果第 1 个分支的逻辑是 “左边界排除中位数”(
left = mid + 1
),那么第 2 个分支的逻辑就一定是 “右边界不排除中位数”(right = mid
),反过来也成立;这种情况的时候选择左中位数,即加一选左。 - 如果第 2 个分支的逻辑是 “右边界排除中位数”(
right = mid - 1
),那么第 2 个分支的逻辑就一定是 “左边界不排除中位数”(left = mid
),反之也成立;这种情况的时候选择右中位数,即减一选右。
- 如果第 1 个分支的逻辑是 “左边界排除中位数”(
- 分支条数只有 2 条,代码执行效率更高,不用在每一轮循环中单独判断中位数是否符合题目要求,写分支的逻辑的目的是尽量排除更多的候选元素,而判断中位数是否符合题目要求我们放在最后进行;
- 注意事项
- 左中位数还是右中位数选择的标准根据分支的逻辑而来,标准是每一次循环都应该让区间收缩,当候选区间只剩下 2 个元素的时候,为了避免死循环发生,选择正确的中位数类型。 如果实在很晕,不防使用有 2 个元素的测试用例,另外在代码出现死循环的时候,建议可以将左边界、右边界、你选择的中位数的值,还有分支逻辑都打印输出一下,出现死循环的原因就一目了然了;
- 如果能确定要找的数就在候选区间里,那么退出循环的时候,区间最后收缩成为 1 个数后,直接把这个数返回即可; 如果你要找的数有可能不在候选区间里,区间最后收缩成为 1 个数后,还要单独判断一下这个数是否符合题意。
6. 模版
1 | # Python: 当分支逻辑不能排除右边界时,选左中位数;如果选右中位数会出现死循环 |
1 | # Python: 当分支逻辑不能排除左边界时,选右中位数;如果选左中位数会出现死循环 |
虽说是两个模板,区别在于选中位数,中位数根据分支逻辑来选,原则是区间要收缩,且不出现死循环,退出循环的时候,视情况,有可能需要对最后剩下的数单独做判断。
7. 二分排序
1 | // 时间复杂度:O(n) * O(logn) = O(nlogn) |