二分查找

二分查找（binary search）在已经排好序的序列中寻找一个分界位置。查找“是否存在”只是它的一种用法：找到第一个不小于目标值的位置，便能同时处理重复值、插入位置和不存在的目标值。这里的输入是可按下标直接访问、按非降序排列的数列；输出是从 0 开始的下标。

一条有序数列的分界

取 $a=(2,4,4,4,7,9,12)$，目标值为 4。下标 0 的值小于 4，从下标 1 起都不小于 4，所以左边界是 1；第一个大于 4 的数在下标 4，所以右边界是 4。等于 4 的元素恰占半开区间 $[1,4)$，出现三次。若改查 5，左右边界都等于 4：5 不在数列中，但应插在下标 4。

左边界停在第一个 4；右边界停在 7 之前。相等元素占据两条边界之间的区间。

半开区间与查找过程

只在 $[lo,hi)$ 内保留尚未判定的位置。左边界查找始终保持两句话：$lo$ 左侧的元素都小于目标值，$hi$ 及右侧的元素都不小于目标值。初始 $lo=0,hi=n$，两边都没有已判定元素，因此条件成立。取 $mid=\lfloor (lo+hi)/2\rfloor$：

• 若 $a_{mid}<x$，从 $lo$ 到 $mid$ 都小于 $x$，把 $lo$ 改成 $mid+1$。
• 若 $a_{mid}\ge x$，从 $mid$ 到原 $hi$ 的右侧都不小于 $x$，把 $hi$ 改成 $mid$。

在上述数列中查 4，三次比较依次发生在下标 3、1、0。区间由 $[0,7)$ 缩到 $[0,3)$、$[0,1)$、$[1,1)$。每次都丢弃至少一个位置；当 $lo=hi$ 时，没有未判定的位置，两侧条件共同确定了第一个不小于 $x$ 的下标。这个结束条件也覆盖空数列，此时直接返回 0。

重复值与未命中

把比较条件改为 $a_{mid}\le x$ 时，左侧留下的是“不大于 $x$”的元素，返回的是第一个大于 $x$ 的位置，即右边界。两个边界之差就是出现次数；左边界小于序列长度且该处恰等于目标值时，目标值才真正存在。只在遇到相等时立刻返回一个下标，无法保证它是重复值中的第一个。

排序条件不能省。若数列是 $(2,7,4)$，上面的左边界程序查 4 会返回下标 1，随后比较 $a_1=7$ 而误判为“不存在”，尽管下标 2 存着 4。二分法则是在连续函数的异号区间内缩小求根范围；两者都对半缩小，但保持的条件不是同一件事。

二分查找的边界移动

观察候选区间、比较位置与被排除的下标。

打开交互演示

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

下面的两个函数不修改输入。lower_bound 与 upper_bound 分别返回左右边界；代码最后的断言就是正文数列的复算。

Python 3

def lower_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def upper_bound(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo


if __name__ == "__main__":
    values = [2, 4, 4, 4, 7, 9, 12]
    assert (lower_bound(values, 4), upper_bound(values, 4)) == (1, 4)
    assert (lower_bound(values, 5), upper_bound(values, 5)) == (4, 4)
    assert (lower_bound([], 4), upper_bound([], 4)) == (0, 0)

代价与使用范围

每轮把候选区间至多缩为原来的一半，故比较次数为 $O(\log n)$，额外只用三个下标，为 $O(1)$ 空间。这一时间界假定下标读取和比较都按常数成本计；链表无法像数组那样直接跳到中点。若要把元素插入 Python 列表，找到位置仍可用二分查找，但移动后续元素通常需要 $O(n)$ 时间，不能把整个插入操作说成对数时间。

参考资料

• TheAlgorithms/Python：binary_search.py：同一仓库的左右边界等实现，本文代码和例子独立编写。
• Python 标准库 bisect 文档：左右插入点与重复值的约定。
• 先修：算法与复杂度；延伸：二分法、最短路径。