找边界,而不只是找到相等值
在已排序数组中,找到一个相等值未必回答了真正问题。若数值出现多次,我们可能需要第一个位置、最后一次出现之后的位置,或出现次数;即使数值不存在,插入位置仍有用。
定义 12.1.1
(下界与上界)
设整数数组 非递减, 为整数。下界是首个满足 的下标 ;若没有,则 。上界是首个满足 的下标 ;若没有,则 。两者均属于 : 是合法边界,但不是数组下标。
等于 的值恰好位于半开区间 ,数量是 。即使 不存在也成立:此时 ,区间为空。
持续记录已知的部分
def lower_bound(a, x):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
输入须为已排序的整数数组,并提供随机访问;程序不会排序或验证输入。每次循环开始时,维持
与 的关系尚未确定的元素位于 。答案边界则仍可能是包含两端的 中任一位置: 不在未知元素区间中,却可以是答案。初始 时,两段已知区域都为空,因此数值条件自然成立,无须读取任何元素,更不用读 。
定理 12.1.2
(下界循环的正确性)
设整数 (), 为整数。每次检验循环条件 时,上述不变量都成立。循环结束时,lower_bound(a, x) 返回 在 中的下界 。
证明
(初始化、保持不变与最后边界)
初始时界限和两个空区间的条件均成立。循环条件 保证整数中点满足 ,所以 存在。
若 ,排序保证所有 均有 。设置 ,便扩大已知小于 的区域,不影响另一区域。否则 ,排序保证所有 都至少为 ;设置 便扩大已知至少为 的区域。两种情况均保留界限。
终止时 。这位置之前的元素全部小于 ,从这位置开始的元素全部至少为 。若位置等于 ,后一区域为空,代表没有元素符合条件。因此返回值恰好是定义中的下界,空数组也成立。
证明透视
排序在哪里被使用,以及更新为何不对称
排序恰好被使用两次,每个分支一次,而且只以这种形式出现:在 作一次比较,便能确定 一侧的所有下标。若数组没有排序, 对 的 没有任何说明。
两个更新刻意不对称。若 ,下标 本身已确定“小于 ”,所以 可以放弃它。若 ,下标 已确定“至少为 ”,但它可能正是第一个这样的下标;因此把 设为 ,让它仍可作为答案。
论证在未知区间 为空,即 时完结。这时两个已确定区域恰好盖住 ,没有空隙也没有重叠,而共同的边界 就是第一个满足 的下标。
不变量也说明:在 插入 仍保持排序。若已有相等元素,插入位置在它们之前。
命题 12.1.3
(上界与相等元素的数量)
对非递减的整数序列, 的上界等于 的下界。等于 的元素恰好位于 中的位置,因此共有 个。
证明
(上界即下一个整数的下界)
对整数而言, 等价于 ,所以满足其中一个条件的第一个下标,也是满足另一个条件的第一个下标。第二个断言:每个 都有 ,每个 都有 ,故都不等于 。当 时,由 与排序得 ,由 得 ,因此 。
概念视角组合
把边界看成计数
在已排序的数组中,小于 的元素构成一段前缀,因此下界恰好就是小于 的元素个数:
对 、,这三个数分别是 、、。二分查找不必逐一查看就能算出这个计数,因为每次比较一次就决定了一整段下标。
例题 12.1.4
(重复值给出两个有用的边界)
令 、。下界循环如下:
| lo | hi | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 0 | 5 | 2 | 2 | hi = 2 |
| 0 | 2 | 1 | 2 | hi = 1 |
| 0 | 1 | 0 | 1 | lo = 1 |
结果为 。求上界时,把条件 a[mid] < x 换成 a[mid] <= x,其余不变。区间依次为 、、、,所以 。相等元素位于位置 1、2、3,共 个。
同一数组若 ,上下界都是 4。没有相等值,但在位置 4 插入 3 仍保持排序。
例题 12.1.5
(边界情况:空数组,以及大于所有元素的值)
对空数组,,初始区间为 ,循环体一次也不执行,不作任何比较便返回 。
再取 、。
| lo | hi | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 0 | 3 | 1 | 3 | lo = 2 |
| 2 | 3 | 2 | 5 | lo = 3 |
两次检验都有 ,所以 移到 ,循环在两次比较后停止。返回值 是正确答案:没有元素至少为 。它是边界而不是下标, 从未被读取。
例题 12.1.6
(用尽最多比较次数的查找)
令 ,,。
| lo | hi | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 0 | 10 | 5 | 12 | lo = 6 |
| 6 | 10 | 8 | 18 | hi = 8 |
| 6 | 8 | 7 | 16 | hi = 7 |
| 6 | 7 | 6 | 14 | hi = 6 |
区间长度依次为 。返回 ,而 确实是第一个至少为 的元素。共作了四次比较,正好等于下文推出的界限 。
终止与成本
每次循环的 都在非空未知区间内。新区间是 或 ,都严格变短。因此非负整数 不断减少,循环必定终止。
定理 12.1.7
(下界循环的终止与比较次数)
设某次迭代开始时,未知区间 的长度为 。迭代后其长度至多为 。因此 时循环至多迭代 次, 时不迭代。每次迭代作一次比较。
证明
(未知区间每次减半)
中点为 ,且 。若 变成 ,新长度为 。若 变成 ,新长度为 。设 为从长度 出发最多的迭代次数,则 ,且 时 。由归纳法, 时 : 时为 ; 时 。
由定理, 时比较次数最多为 ;空数组不作比较。若随机访问和整数比较均为常数时间,时间为 ,额外空间为 。这不是对必须从头遍历才能索引的链表、昂贵比较或预先排序成本的保证。
在固定宽度整数中,lo + (hi - lo) // 2 避免直接相加两个可能很大的下标,但前提是非负界限及其差值都能由所选下标类型表示。Python 整数不会溢出;其他语言仍需选择适当类型。
常见边界错误
反例模式
把闭区间循环与排他的上界混用
假设程序以 hi = len(a) 开始,却使用 while lo <= hi,中点访问保持不变。对 、,第一次比较后 lo=1;下一次循环会读取超出数组的 a[1]。 可以是答案,但不是可读元素。
闭区间和半开区间写法都可以正确,但初始界限、循环条件、更新方式和证明必须一致。只改动正确版本中的一个符号,并不会自动保留不变量。
常见错误
(把返回的边界当作 存在的证明)
无论 是否出现,下界 都有定义。若 ,则 不存在;若 ,也可能 。对 、,结果是 ,但 。 存在,当且仅当 且 ,即 。
常见错误
(把上界当成最后一次出现的位置)
上界是最后一个相等元素之后的位置。对 、,上界是 ,而最后一次出现在下标 。这个公式只在 时成立;若 不存在, 可能是较小的值,而 时它根本不是下标。
练习与解答
快速检查
(对 ,求 和 的上下界。)
按定义:第一个满足条件的下标,若没有则为 。
解答 · 答案
的上下界均为 ; 的上下界均为数组长度 。两者都不读取哨兵元素。
快速检查
(对 、,上下界各是多少?)
用 计算相等元素的数量。
解答 · 答案
分别为 和 ,差值 是相等元素的数量。
快速检查
(若 ,为什么下界算法设置 hi = mid 而非 hi = mid - 1?)
想一想 本身会不会是答案。
解答 · 答案
中点本身可能是第一个符合位置。保留它作为未知区间的末端,可保留这个候选答案;例如 查找 时,第一个中点是 ,但减一会令 hi=0,错误返回 。
快速检查
(程序用上界条件得到 ,可以读取 吗?)
回想 取哪些值时才是下标。
解答 · 答案
不可以。 表示没有元素大于 ;非空数组的最后合法下标是 。
证明查找程序时,须交代答案契约、已知区域与边界的确切处理。短小的循环之所以可靠,是因为每次更新都保留这些含义。