动机
二分搜索不一定是在数组中寻找某个键。有时,未知答案是一个数:容量、允许的延迟,或最大的负载。试探一个数,可以回答一个“是否可行”的问题。如果一个数可行后,所有更大的数也可行,那么这些真假答案之间就有一条可以用二分搜索定位的边界。
这里有两项不同的证明责任。首先,必须证明判定过程确实回答了原来的可行性问题;其次,必须证明查找过程始终保留第一个可行值。围绕错误判定进行快速查找,仍然会得到错误答案。下面以固定顺序的非负负载分成连续块为例,完整建立这两个论证。
定义与计算模型
定义 1.3.1
(单调谓词与边界)
设整数 。这里称整数下标 上的谓词 为单调,是指只要 ,那么对每个 都有 。边界 是第一个取真值的下标;若所有下标都为假,则定义 。因此 ,小于 的下标全为假,定义域中不小于 的下标全为真。
整个查找期间,谓词必须固定:一次求值不能改变后续查询的真假。实现可以从输入计算 ,不必实际存储一个布尔数组。整数 是边界哨兵,不是可以查询 的下标。
先采用字 RAM 模型,假设下标、区间差和所需算术量都能放进常数个机器字。数组访问和机器字上的算术为常数时间。一次 调用有自己的代价,不能自动把它当作一条机器指令。
边界查找定理
定理 1.3.2
(寻找第一个真值,也允许没有真值)
对定义在 个下标上的任意单调谓词 ,下列算法返回边界 。谓词调用次数至多为 ;除谓词自身的工作空间外,算法只需常数额外空间。
lo = 0
hi = N
while lo < hi:
mid = lo + floor((hi - lo) / 2)
if P(mid):
hi = mid
else:
lo = mid + 1
return lo
不变量记录已经排除的区域
证明
(边界查找:不变量与终止)
保持 ,以及两项断言:定义域中小于 的下标全为假;定义域中不小于 的下标全为真。这也等价于未知边界满足 。初始时,两个外侧区域都是空集,因此全假或全真的情形也满足不变量。
若 为真,单调性说明后面的定义域下标全为真。令 保持不变量,并保留 作为可能答案。若 为假,那么前面不可能出现真值,否则单调性会迫使 为真。因此令 也保持不变量。两端相遇时,由 得 。
循环执行时,,所以每次查询都在定义域内。非负整数宽度 严格减小,新宽度至多为 。经过 次迭代后,宽度至多为 。取 ,便有 ,所以宽度为零。若 ,不执行任何迭代或查询,直接返回零。
证明透视
中点为真时,它仍可能是答案
赋值 并不是说中点错误,而是说严格位于中点之后的位置不可能是第一个真值。答案的剩余候选是闭整数区间 ;实际查询的中点却位于半开下标区间 。区分这两个角色,就能理解更新方式以及哨兵 的作用。
若每次谓词求值至多需要 次字操作,预处理代价为 ,总时间就是 。调用次数为对数级,并不自动推出运行时间为对数级。中点写法避免将两个端点相加,但表示范围仍须容纳端点差及算法的其他算术结果。
可行性问题:连续负载分块
给定非负整数 ,其中 ,并给定 。分块由端点
描述。第 块包含下标 的连续元素,其负载为这些元素之和。每个元素恰好出现一次,输入顺序固定,各块非空。目标是最小化各块负载的最大值。端点选择只有有限种,所以最优解存在。
对整数容量 ,令 表示:存在合法分块,使每块负载至多为 。在容量 下可行的同一个分块,在更大容量下仍然可行,因此 单调。这个结论来自问题定义,还不需要选定判定算法。
贪心可行性判定
从左往右扫描。只要当前块加上下一元素仍不超容量,就加入;否则结束当前块,用该元素另开一块。若某个元素本身大于 ,立即拒绝,因为包含它的非负负载块不可能满足容量限制。
feasible(B):
blocks = 1
load = 0
for x in a, in the original order:
if x > B:
return false
if load + x > B:
blocks = blocks + 1
load = x
else:
load = load + x
return blocks <= k
这个过程不会产生空块。尤其是第一个元素通过拒绝检查后,一定能放进初始的空当前块。所有实际构造出的块都满足容量限制,所以接受时确实可行。较难的方向是:拒绝时,不存在另一种更好的切点安排。
定理 1.3.3
(贪心判定使用最少的块数)
若每个 ,上述贪心扫描构造的可行分块,其块数最少。因此 feasible(B) 返回真当且仅当 成立。
证明:比较已经到达的端点
证明
(贪心端点从不落后)
令 为贪心算法处理完第 块后到达的端点,;扫描结束后,将后续所有 定义为 。任取另一可行分块,其端点为 。证明对 有 。
假设 。若已经有 ,由于贪心端点不减,结论直接成立。否则,从 到 的一段,是另一分块第 块的后缀。元素非负,说明后缀负载不大于整块负载,因此至多为 。
从 开始的贪心块会延伸到最远的可行端点:一旦加入下一项使负载超过 ,再加入更多非负项也不能恢复可行。它因而至少到达 ,完成归纳。取 ,有 ,说明贪心至多使用 块。竞争分块是任取的,所以贪心块数最少。
证明透视
非负性与端点比较用在哪里
归纳比较的是:用同样多的块后,贪心覆盖的位置与任何可行分块覆盖的位置;它从不声称两者的切点相同。非负性用了两次。第一,竞争分块的第 块中,从 开始的一段是后缀,而由非负元素组成的块,其后缀负载不大于整块,因此至多为 。第二,下一项使当前贪心负载超过 之后,再加入更多项也无法降低负载,所以贪心块停在最远的可行端点。假设 保证从未到末尾的位置开始的贪心块至少含一个元素。归纳在 时收尾: 表示贪心至多用 块,无论竞争分块的可行块数 是多少。若有负项,后缀性质失效;下面的反例显示扫描会拒绝一个其实可行的容量。
搜索最优容量
先计算
任何可行容量都不小于 ,因为含有最大元素的块,其负载至少为该元素。容量 可行:把整个序列作为一块即可。因此最优容量 是区间 中的整数。
用同一循环,初始化 lo = L、hi = S,并以 feasible(mid) 作为 P(mid)。初始上界已经可行,不变量为 。每条分支都由已经证明的判定支持,所以终止时返回 。无须实际查询 。若 ,循环不调用谓词,但预处理仍然需要时间。
一次可行性判定扫描 项,用 次字操作和常数工作空间。调用次数 ,所以计算上下界并查找的总字操作数为
最后在容量 下再扫描一次,记录贪心切点,即得到见证分块。这增加 时间及至多 个输出字;查找本身仅需常数额外字。空间界不包含输入数组。
概念视角算法
把贪心测试看成沿前缀和的跳跃
设 ,这是一个非递减数组,。当 时,从端点 开始的贪心块结束于满足 的最大 ,而测试成功当且仅当 次跳跃 能到达 。每次跳跃本身就是对单调谓词 的边界搜索,所以经 预处理之后,一次测试只需 ,而不是 。
算术假设允许我们忽略什么
字操作界要求安全存储 、下标,甚至可能超过当前容量的试探和 load + x。对于无界二进制输入,不能默认这些运算都是常数时间。若每项至多有 位,则 位足以存储这些负载、试探和及计数器。简单二进制实现中,每次加法或比较需要 位操作,搜索至多有 轮;包含预处理后,得到上界 。这是关于二进制输入长度的多项式上界,并不是说位运算没有代价。
例题
例题 1.3.4
(同时跟踪查找与判定)
序列为 ,,初始 、。容量 时,贪心得到 与 ,因此令 。中点 需要 、、 三块,所以令 。中点 可行,令 ;中点 需要三块,令 。两端相遇于 ,见证负载分别是 和 。最后一个不可行容量 ,结合单调性,证明更小容量都不可行。
例题 1.3.5
(重复元素也是边界问题)
在有序数组 中,取 为 ,第一个真值下标为一。改用 ,边界为四。两边界之差三,就是元素二的出现次数。没有元素满足条件时,边界为 ;它是合法返回位置,却不是合法数组访问下标。
例题 1.3.6
(零负载不需要正容量)
对于 与 ,有 。查找不调用谓词,直接返回零;见证扫描只使用一块 。问题允许至多两块。若要求恰好两块,还须增加一个切点,不过最优值仍为零。
常见错误
反例模式
负负载破坏这个贪心证明
取 、、。整个序列的负载为四,所以一块可行。但贪心在第二个四之前结束第一块,结果使用两块。允许负项后,暂时超容量的前缀可能在后面恢复可行。由分块存在性定义的谓词仍然对 单调,失效的是计算该谓词的这个算法。
常见错误
(把连续分块的证明用于重排后的负载)
顺序也是实际假设,并不是外观上的限制。对于 和 ,最优连续分块的最大负载为 ,在第二项后切开即可达到。若允许重排, 与 的最大负载是 。连续分块的证明不能直接解决任意分配问题。
常见错误
(把下界移到中点)
在假查询后赋值 lo = mid 可能不终止:当上下界为零和一时,中点为零,区间可以完全不变。为假的中点已被排除,所以正确的更新是 lo = mid + 1。
常见错误
(对非单调谓词做查找)
循环每一轮也许都会终止,却仍可能丢弃答案。对真假序列 [true, false, true],算法首先查询中间项,得到假并令 ;随后返回 ,但第一个真值其实是 。单调性正是每个被丢弃区域的依据。
总结
边界查找之所以正确,是因为固定的单调谓词为每次排除区域提供依据。将最优化转成可行性问题,还需要证明判定过程本身。对于非负连续负载,贪心端点比较完成这一证明;二分搜索随后通过对数次线性扫描,找到最优容量。
练习
快速检查
(跟踪 [false, false, false] 上的边界查找。若三项全真,结果如何?解释空定义域的情况。)
解答 · 答案
从 开始。下标一为假,得到 ;下标二为假,得到 ,返回哨兵三。若全真,查询一和零后依次得到 、,返回零。若 ,直接跳过循环,边界同样为零。这些情况都不需要定义域外的查询。
快速检查
(用两次边界查找计算有序数组中目标 的出现次数,包含目标不存在的情况。)
解答 · 答案
求 为第一个满足 的下标,求 为第一个满足 的下标;相应谓词全假时返回 。有序性保证两个谓词都单调。恰好是 中的元素等于 ,所以出现次数为 。目标不存在时,两边界相等,也允许它们都等于 。
练习 1.3.7
(对 、 求最优容量。给出可行分块,并证明更小容量不可能。)
核心
解答(3)
- 1
从下方限制容量
任何可行容量都不小于 。
依据: 含有元素 的块,其负载至少为 。
- 2
在容量 下给出分块
关键一步
连续块 、、 的负载为 、、,都不超过 ,且共有三块,所以 成立。
- 3
得出最优容量为
容量 可行,更小的容量都不可行,因此 。这个证书不必再列完整的查找过程。
快速检查
(指出贪心证明的哪些具体步骤使用了非负性。为什么仅有 的单调性不足以证明扫描正确?)
解答 · 答案
从一个块中删去前面的非负元素后,后缀负载不大于整块;另外,加入下一项导致超容量后,继续加入非负项不可能降低总和。这两点都使用非负性。存在性谓词的单调性只支持寻找它的边界,并不保证任意候选判定程序都能计算它。负项反例区分了这两件事。
练习 1.3.8
(当 时,证明恰好分成 个非空块,与至多分成 块具有相同最优容量。 时有什么问题?)
核心证明
解答(3)
- 1
从使用 块的可行分块出发
因 ,至少有一块包含两个元素。
- 2
把该块分成两个连续的非空部分
关键一步
新分块有 块,容量界不变。重复直到恰好有 块。
依据: 元素非负,每个新块的负载都不超过原块的负载。
- 3
比较两个最优值
∎恰好 块的分块也是至多 块的分块;上面的拆分又在不提高容量下给出相反方向,所以两个最优值相同。若 ,恰好 个非空块不可能,但至多 块仍然可行。
快速检查
(若可行性判定每次需要 时间,进行 次调用的二分搜索是否只需 时间?给出包含预处理代价 的合理上界。)
解答 · 答案
必须计入每次调用的实际代价和循环开销。对于 ,在题设的每次调用代价与字操作假设下,上界为 。调用次数是对数级,不代表调用内部消耗的时间也是如此。若搜索范围可能只有零或一个候选,可用 并保留常数开销。