Binary Search, Lower Bound, Upper Bound

Posted on

BinarySearch “Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky.” – Donald Knuth

基本思想

将有序数组分为左右两个区域，左边区域比目标值小、右边区域比目标值大，利用数组的有序性折半查找中间的分界位置。如果分界位置刚好是目标则找到目标，否则为没有找到。

复杂的边界条件

真实的情况的边界条件往往比较复杂，假设有下面一个有序数组：

[1,2,3,5,5,5,8,9]

边界值为 5，需要求得下面四个结果：

  1. 找到第一个”>=5”的元素(第一个 5)
  2. 找到最后一个”<5”的元素(3)
  3. 找到第一个”>5”的元素(8)
  4. 找到最后一个”<=5”的元素(第三个 5)

上面四个问题，如果用二分查找法，那么边界条件(< 还是 <=)、边界迭代过程(l=mid 还是 l=mid+1)都会比较复杂。

通用的二分查找模板

l, r := -1, N
for l+1 < r {
    m := (l+r)>>1
    if isLeft(m) {
        l = m
    } else {
        r = m
    }
}
return l or r

  • 上面算法在 l、r 二分靠近边界时，始终保持 l、r 指针所属区域不改变(l 始终在左区域、r 始终在右区域)，这样逻辑比较简单。

  • 细节 1: 为什么 l 的初始值为-1、r 的初始值为 N？ 如果所有元素都为”左区域”或”右区域”则初始值就是错误值，最终结果也是错误值。

  • 细节 2: m 是否始终处于[0,N)以内？ $m_{min}=(-1+1)/2=0$ $m_{max}=((N-2)+N)/2=N-1$ m 在[0,N-1]范围，所以始终有效

  • 细节 3: 迭代更新时，能否写成l=m+1或r=m-1? 如果刚好在边界，这样的操作可能导致 l 或 r 指向错误的区域(如 l 指向右区域)，所以应该写成l=m。 除非最后返回值本身允许跨区域，这种可以特殊处理。

  • 细节 4: 会不会陷入死循环？ 条件l+1 < r，所以 m 一定不会和 l 或 r 相等，所以不会陷入死循环。

  • 再来看题目：[1,2,3,5,5,5,8,9]，边界值为 5，求目标值

序号 目标条件 示例元素 isLeft 条件 返回值 对应 C++中 STL
1 第一个”>=5”的 第一个 5 < 5 r lower_bound()
2 最后一个”<5”的 3 < 5 l lower_bound()-1
3 第一个”>5”的 8 <= 5 r upper_bound()
4 最后一个”<=5”的 第三个 5 <= 5 l upper_bound()-1

二分查找解题一般流程

  1. 建模：将有序数组划分为左、右区域，确定isLeft(m)的条件
  2. 确定返回l还是r
  3. 套用上面的算法模板
  4. 根据实际情况调整最后的结果