二分：每次砍掉一半

从猜数说起

心里想一个 1 到 100 之间的整数，让别人来猜。他每猜一个，你只回答「大了」或者「小了」。最少的猜法是从 50 开始：无论答案是「大了」还是「小了」，候选取值范围都立刻只剩一半。100 个数最多 7 次就能猜到。

这套方法的英文名是 binary search，中文常译作二分查找，也叫折半查找。它把「在一批数据里找某个值」的代价从「看一个排除一个」压成「看一个排除一半」。

上一课的归并排序每切一层规模减半，深度是 \lceil \log_2 n \rceil + 1；二分查找用的是同一个形状，只是「切」发生在查找过程中。

有序性与单调性

二分查找有一条前提：数据必须有序。

这条前提的作用是让「比较一次」能推出「排除一半」。在有序数组里读到 a[mid]，就能断定：所有下标小于 mid 的元素都不大于它，所有下标大于 mid 的元素都不小于它。猜数游戏里的「大了」与「小了」正是这条性质在说话。

若数组无序，「大了」这个回答什么都推不出来——被排除的那一半里可能就藏着答案。所以二分的第一个动作是确认数据有序，无序就先排序（上一课的代价是 O(n \log n)，排一次可以供很多次查询复用）。

闭区间模板

先看最直接的一种写法：待查找的区间用闭区间 [lo, hi] 表示，两端都可能是答案。

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

四行关键代码给出了循环不变式。这句话要这样读：若 x 在数组里，它的下标一定落在闭区间 [lo, hi] 内。它在每次循环开始前都成立。

按这句话把每一行推出来：

不变式怎么用

拿 a = [1, 3, 5, 7, 9, 11] 找 7，把每一轮的状态打出来：

a = [1, 3, 5, 7, 9, 11]
x = 7
lo = 0
hi = len(a) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    print(f'lo={lo} hi={hi} mid={mid} a[mid]={a[mid]}  区间 {a[lo:hi + 1]}')
    if a[mid] == x:
        print('命中，返回', mid)
        break
    if a[mid] < x:
        lo = mid + 1
    else:
        hi = mid - 1

lo=0 hi=5 mid=2 a[mid]=5  区间 [1, 3, 5, 7, 9, 11]
lo=3 hi=5 mid=4 a[mid]=9  区间 [7, 9, 11]
lo=3 hi=3 mid=3 a[mid]=7  区间 [7]
命中，返回 3

三行输出里，打印出来的区间一轮比一轮短，而 7 始终在里面——这就是不变式在起作用。第三行的区间只剩一个元素，靠的正是 while lo <= hi 里的那个等号。

写完二分之后，用一组边界数据逐条验一遍，比反复读代码有效得多：

for name, arr, x in [('空', [], 1), ('单元素命中', [5], 5), ('单元素不中', [5], 3),
                     ('全相同命中', [7] * 6, 7), ('全相同不中', [7] * 6, 8),
                     ('目标在左端', [1, 3, 5, 7, 9], 1), ('目标在右端', [1, 3, 5, 7, 9], 9),
                     ('目标不存在', [1, 3, 5, 7, 9], 4)]:
    k = bsearch_closed(arr, x)
    print(f'{name}：返回 {k}，真的在里面吗 {x in arr}')

空：返回 -1，真的在里面吗 False
单元素命中：返回 0，真的在里面吗 True
单元素不中：返回 -1，真的在里面吗 False
全相同命中：返回 2，真的在里面吗 True
全相同不中：返回 -1，真的在里面吗 False
目标在左端：返回 0，真的在里面吗 True
目标在右端：返回 4，真的在里面吗 True
目标不存在：返回 -1，真的在里面吗 False

八条全对。这八条覆盖了最容易出问题的位置：空数组、只有一个元素、所有元素相同、答案在两端、答案不在。

左闭右开模板

第二种写法换个约定：区间用左闭右开 [lo, hi) 表示，hi 本身不是候选。它适合回答「第一个不小于 x 的位置在哪里」这类问题：

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

两种约定的差别集中在三处，对照着看就不会混：

左闭右开版的返回值要额外解释一句：它返回的是插入位置，不是「是否找到」。x 不存在时它照样返回一个合法下标（0 到 len(a) 之间），所以判断存在性要在外面补一步：

k = lower_bound(a, x)
found = k < len(a) and a[k] == x

这两步里的 k < len(a) 不能省：x 比数组里所有元素都大时 k 正好等于 len(a)，直接取 a[k] 会越界。

三种常见的错法

边界写错很少会报错，多数时候它安静地给出错误答案，或者干脆不结束。把三种错法跑一遍，比读十遍描述有用。

错法一：mid 之后区间没有收缩。

def bug_no_shrink(a, x):
    lo = 0
    hi = len(a)
    steps = 0
    while lo < hi:
        steps += 1
        if steps > 50:
            return '步数超限，死循环', steps
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid
        else:
            hi = mid
    return lo, steps

print(bug_no_shrink([1, 2, 3], 5))

('步数超限，死循环', 51)

hi = lo + 1 时 mid 正好等于 lo，而 a[mid] < x 又把 lo 赋值成 mid，区间长度一直不变，循环永远出不来。lo = mid + 1 与 hi = mid 这两处的差别就在这里：一处加一、一处不加，写法由区间开闭决定。

错法二：闭区间配上 while lo < hi，漏掉最后一个元素。

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

for x in (1, 3, 5, 7, 9):
    print(f'找 {x}: 缺陷版 {bug_lose_last([1, 3, 5, 7, 9], x):>3}  正确版 {bsearch_closed([1, 3, 5, 7, 9], x):>3}')

找 1: 缺陷版   0  正确版   0
找 3: 缺陷版  -1  正确版   1
找 5: 缺陷版   2  正确版   2
找 7: 缺陷版   3  正确版   3
找 9: 缺陷版  -1  正确版   4

同一个函数在五个目标上错了两个。答案藏在「停下时区间里还剩谁」：剩下的是 1 或 5 或 7 的那些情况，缺陷版恰好在循环里碰到过它们；剩下的是 3 或 9 的那些情况，它们从没被检查过就被丢掉了。这类错在随机测试里很容易蒙混过去，要专门拿「答案在两端」的数据去试。

错法三：目标不存在时返回一个错误的下标。

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

arr = [10, 20, 30]
for x in (5, 20, 25, 30, 40):
    k = bug_no_check(arr, x)
    print(f'找 {x:>2}: 返回下标 {k}，该位置的值是 {arr[k] if k < len(arr) else "越界"}')

找  5: 返回下标 0，该位置的值是 10
找 20: 返回下标 1，该位置的值是 20
找 25: 返回下标 2，该位置的值是 30
找 30: 返回下标 2，该位置的值是 30
找 40: 返回下标 3，该位置的值是 越界

返回的下标看起来都很合理，其中三个却是错的下标（找 5 与 25 给出的位置值不等于目标），找 40 还越了界。判分的断言若只写「返回值在 0 到 n 之间」，这种错法一路通过。

重复元素与 bisect

数组里有重复元素时，「找到了」这句话本身就不完整——要找的是第一个，还是最后一个？

import bisect

b = [1, 2, 2, 2, 2, 3, 4]
print('第一个 2 的下标 bisect_left =', bisect.bisect_left(b, 2))
print('越过 2 的下标 bisect_right =', bisect.bisect_right(b, 2))
print('我的 lower_bound  =', lower_bound(b, 2))
print('2 一共出现', bisect.bisect_right(b, 2) - bisect.bisect_left(b, 2), '次')

第一个 2 的下标 bisect_left = 1
越过 2 的下标 bisect_right = 5
我的 lower_bound  = 1
2 一共出现 4 次

标准库的 bisect 提供的正是这两个位置：bisect_left 给出第一个不小于 x 的位置（等于自己写的 lower_bound），bisect_right 给出所有等于 x 的元素之后的位置。两者之差就是 x 出现的次数，这一条在做统计类题目时很省事。

用 bisect 对照自己写的模板，是检查边界最省力的办法：拿一批随机有序数组，对每个目标同时跑自己写的版本与 bisect，不一致就打印那组数据。

为什么是对数

每比较一次，候选区间就减半。n 个元素的区间最多经历 \lceil \log_2 (n+1) \rceil 轮。

把轮数数出来：

for n in (10, 1000, 100000, 2000000):
    a = list(range(n))
    worst = 0
    for x in (0, n // 3, n // 2, n * 3 // 4, n - 1, n + 5):
        lo = 0
        hi = len(a)
        c = 0
        while lo < hi:
            c += 1
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        if c > worst:
            worst = c
    print(f'n={n:>8}  最多 {worst:>2} 轮')

n=      10  最多  4 轮
n=    1000  最多 10 轮
n=  100000  最多 17 轮
n= 2000000  最多 21 轮

规模从一万涨到两百万，是两百倍，轮数只从 17 涨到 21。这就是对数的形状：n 翻倍，轮数只加一。

换成时间看，两百万元素的数组，找最后一个元素：

相差约 1.1 万倍。做 100000 次二分查询一共 0.288956 秒，平均每次不到三微秒。

二分的代价还有个前提值得记下：它要求按下标随机访问，每次比较都要取 a[mid]。第 3 课讲过，按下标取元素是 O(1)，这一条在列表上成立。若数据存在链表这类不能按下标直接取的结构里，二分就不适用了。

这一课用到的判断

• 用二分之前先确认有序。无序就先排序，排一次供多次查询复用。
• 先写不变式，再写边界。「答案一定在区间里」这句话能把初值、循环条件、两处收缩全部推出来，不用试。
• 闭区间与左闭右开各自成套。初值、循环条件、收缩写法要配套；混用就会出现这一课那三种错法。
• 目标不存在时，二分只能给出插入位置。判断存在性要补一步 k < len(a) and a[k] == x。
• 有重复元素时先明确要第一个还是最后一个。第一个用 bisect_left（等于自写的 lower_bound），最后一个用 bisect_right；两者之差是出现次数。
• 验证靠边界数据：空、单元素、全相同、答案在两端、答案不存在，五类各一条。
• 二分把线性扫描压成对数级。规模翻倍只加一轮，这是它值得优先考虑的原因。

• Python 官方文档 · bisect官方文档 · bisect_left 与 bisect_right 的语义、性能说明
• 《算法（第 4 版）》第 1 章 基础（二分查找）书 · 二分查找的推导与图示；当参考书查