居合斩！二分查找

Posted on

算法解释

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为 O(n) 的数组，二分查找的时间复杂度为 O(logn)。

具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍：

  • 尝试熟练使用一种写法，比如左闭右开（满足 C++、Python 等语言的习惯）或左闭右闭（便于处理边界条件），尽量只保持这一种写法。
  • 在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。

二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题，指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度。

求开方

69. Sqrt(x)

mid = (lo + hi) // 2 可能会因为 lo + hi 溢出而错误，因而采用 mid = lo + ((hi - lo) >> 1) 的写法。

另外，这道题还有一种更快的算法——牛顿迭代法：

1
2
3
4
5
6
def sqrt(x):
    num = x
    while num * num > x:
        num = (num + x // num) // 2
    
    return num

查找区间

34. Find First and Last Position of Element in Sorted Array
这道题可以看作是自己实现 Python 里的 bisect_left 和 bisect_right 函数。

查找峰值

162. Find Peak Element
在确保两端不是峰值后，若当前中点不是峰值，那么其左右一侧一定有一个峰值。

旋转数组查找数字

81. Search in Rotated Sorted Array II
注意，因为数组存在重复数字，如果中点和左端的数字相同，我们并不能确定是左区间全部相同，还是右区间完全相同。在这种情况下，我们可以简单地将左端点右移一位，然后继续进行二分查找。

练习

154. Find Minimum in Rotated Sorted Array II
旋转数组的变形题之一。

540. Single Element in a Sorted Array
在出现独立数之前和之后，奇偶位数的值发生了什么变化？

4. Median of Two Sorted Arrays
需要对两个数组同时进行二分搜索。