外观
06 - 二分查找不只是在数组里找数:边界与答案搜索
前置阅读:01 - 时间复杂度如何决定系统上限、A - 算法正确性、测试与基准方法。
后续应用:23 - 序列动态规划中的 LIS 最小结尾优化。
摘要
按时间排序的日志中,目标时间可能不存在,也可能对应多条记录。二分查找可以找到第一条不早于目标时间的记录,每次比较都排除约一半尚未确定的范围。本文先解释边界查找的基本模型,再推导区间更新规则,最后把同一思路用于寻找最小可行容量。
1. 场景:找到第一条不早于目标时间的日志
数组已按时间升序排列,需要找第一条 timestamp >= target 的记录。这里的升序允许相等值,也称非递减。Lower Bound(下界查找)返回第一个大于等于目标值的位置;即使目标值不存在,也能确定从哪里开始读取日志。
例如时间戳为 [10,20,20,30],目标为 20 时应返回下标 1,目标为 25 时应返回下标 3。若目标为 40,则返回数组长度 4,表示没有符合条件的记录;这个结果是位置,不能直接用来访问数组。
二分能缩小范围,是因为数据有序:若中点值小于目标,中点及其左侧都不符合条件;若中点值大于等于目标,答案只可能在中点或更左的位置。把条件 values[i] >= target 的判断结果写出来,就是一段 false 后接一段 true,其中任一段都可以为空。查找的目标是两段之间的边界。
2. 左闭右开模板
下面是需放入 Java 类中的局部方法,要求 values 非 null 且按非递减顺序排列。[left, right) 表示包含 left、不包含 right 的待检查元素区间,因此初始 right 可以等于数组长度。返回的边界位置允许等于 right,并不一定对应一个数组元素。
java
static int lowerBound(long[] values, long target) {
int left = 0;
int right = values.length; // 搜索区间 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (values[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}循环不变量是每轮循环前后都成立的约束。这里可以写成:[0, left) 中的值全部小于 target,[right, values.length) 中的值全部大于等于 target。两段之外的元素尚待检查,答案位置始终在 [left, right] 内。
- 若
values[mid] < target,有序性保证下标不大于mid的值都小于目标,所以令left = mid + 1。 - 否则,
mid及其右侧都满足条件,但还需寻找更早的位置,所以令right = mid。虽然mid不再进入待检查区间,它仍作为右边界保留,是可能返回的答案。
当 left < right 时,left <= mid < right,两种更新都会严格缩小待检查区间。最终 left == right,所有更早的值都小于目标,所有从该位置开始的值都大于等于目标,这就是插入目标后仍保持有序的位置。空数组返回 0。长度为 n 时,每轮约缩小一半,查找时间为 O(log n)(空数组为常数时间),额外空间为 O(1)。
Upper Bound(上界查找)返回第一个严格大于 target 的位置。它把“不满足条件”的判断从 < target 改为 <= target,其余规则相同。下面的局部方法同样要求非 null 的有序数组:
java
static int upperBound(int[] values, int target) {
int left = 0;
int right = values.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (values[mid] <= target) left = mid + 1;
else right = mid;
}
return left;
}在同一有序数组上分别求出这两个位置后,target 的出现区间就是 [lowerBound, upperBound),出现次数为二者之差;目标不存在时,两者相等。前面的 Lower Bound 片段接收 long[],Upper Bound 片段接收 int[],组合使用时需要统一数组类型;第 5 节提供了 int[] 版 Lower Bound。
这两种查找都在寻找“第一个满足条件的位置”。这种返回真假的条件也称谓词;只有判断结果按顺序从 false 变为 true、不会再变回去时,才能用这里的更新规则。
3. 为什么不能写 mid = (left + right) / 2
Java 的 int 有取值上限,两个合法的大下标相加仍可能溢出,导致中点错误甚至越界。对于本文非负且 left <= right 的下标,先计算差值再加回左边界,可以避免这个加法溢出:
java
int mid = left + (right - left) / 2;4. 对答案进行二分
数组查找是在已有元素中找边界。答案二分则把候选答案按大小排列,再逐个判断是否可行,不必真正创建这个数组。假设容量 x 可行时,所有大于 x 的容量也可行,就会形成如下判断结果:
text
false false false true true truefeasible(x) 是可行性判断函数,返回容量 x 能否满足要求。第一个 true 对应最小可行容量。这里的单调性指可行性只从不可行变为可行,不会随着容量增大再次变为不可行。
答案二分成立还需要:
- 可行性在搜索区间内单调;
- 初始区间确实覆盖答案;
feasible本身正确且成本可接受;- 整数、浮点或离散答案的终止条件分别定义清楚。
若一次可行性检查为 O(n),整数答案二分通常记为 O(n log R),其中 R 是候选整数的数量,而不是输入元素个数。包含初始化且兼顾只有一个候选的情况,可以写成 O(n(1 + log R))。下面只讨论整数答案;浮点答案需要另行规定误差或迭代次数,不能直接沿用整数的终止条件。
例如:包裹必须按给定顺序运输,每个包裹不可拆分,每天的载重不超过容量,求在 days 天内运完的最小运力。下面的局部片段假设 weights 非 null、非空,重量为正数,days >= 1,且总重量不超过 int 上限;它没有校验这些输入条件。
最小容量至少是最重包裹的重量,否则该包裹一天也运不走。总重量则是可行上界,因为这个容量能在一天内运完。因此最小答案在闭区间 [left, right] 内。这里 right 是一个可行容量,不是数组模板中不参与检查的下标,两者的区间含义要分别理解。
canShip 按顺序装载,只有下一个包裹放不下时才开启新的一天。在顺序固定、重量为正的前提下,第一天尽量多装不会增加剩余工作;逐天采用同样的规则,得到的是该容量所需的最少天数。容量增大后,原有装载方案仍可使用,所以可行性具有二分所需的单调性。
java
static int minCapacity(int[] weights, int days) {
int left = 0;
int right = 0;
for (int w : weights) {
left = Math.max(left, w);
right += w;
}
while (left < right) {
int mid = left + (right - left) / 2;
if (canShip(weights, days, mid)) right = mid;
else left = mid + 1;
}
return left;
}
static boolean canShip(int[] weights, int days, int capacity) {
int usedDays = 1;
int load = 0;
for (int w : weights) {
if (load + w > capacity) {
usedDays++;
load = 0;
}
load += w;
}
return usedDays <= days;
}mid 可行时,最小答案不大于它,令 right = mid;不可行时,所有更小容量也不可行,令 left = mid + 1。两端相遇时,就确定了最小可行容量。
若总重量可能超过 int,容量边界、中点和当天累计载重都应使用 long,否则上界累加或 load + w 可能溢出。第 5 节展示了对应写法。canShip 依赖调用方保证容量不小于最重包裹;不要把它当作能校验任意容量的通用接口。
5. 完整可运行示例:精确查找、边界与答案二分
下面的类对应文件名 BinarySearchDemo.java,包含 main 入口。数组查找要求非 null 且有序,运力计算沿用上一节的正重量、非空数组和合法天数前提,并用 long 累加。本文未编译或运行此示例,也未核对具体 JDK 版本。
exact 在找到相等值后立即返回,因此重复值存在时不保证返回第一个位置;找不到返回 -1。它采用闭区间 [left, right],所以使用 left <= right,并在排除中点时更新为 mid ± 1。Lower Bound 要继续寻找边界,不能混用这套规则。
java
import java.util.Arrays;
/**
* 可运行示例:二分查找不只是在数组里找数:边界与答案搜索。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class BinarySearchDemo {
static int exact(int[] a, int target) {
// 精确查找采用闭区间 [left, right]。
int left = 0,
right = a.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (a[mid] == target) return mid;
// mid 已确认不是答案,因此从下一轮区间中排除。
if (a[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
static int lowerBound(int[] a, int target) {
// Lower Bound 采用左闭右开区间 [left, right)。
int left = 0,
right = a.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] < target) left = mid + 1;
// 否则 mid 满足条件,仍可能是第一个满足条件的位置。
else right = mid; // 将 mid 保留为可能返回的右边界。
}
return left;
}
static long minCapacity(int[] weights, int days) {
long left = 0,
right = 0;
for (int weight : weights) {
// 下界是最重包裹,上界是一次运完的总重量。
left = Math.max(left, weight);
right += weight;
}
while (left < right) {
long mid = left + (right - left) / 2;
// 可行性具有单调性:mid 可行时,所有更大容量也可行。
if (canShip(weights, days, mid)) right = mid;
else left = mid + 1;
}
return left;
}
static boolean canShip(int[] weights, int days, long capacity) {
int used = 1;
long load = 0;
for (int weight : weights) {
if (load + weight > capacity) {
used++;
load = 0;
}
load += weight;
}
return used <= days;
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
int[] sorted = { 1, 2, 2, 2, 5, 9 };
System.out.println(exact(sorted, 5));
System.out.println(lowerBound(sorted, 2));
System.out.println(minCapacity(new int[] { 3, 2, 2, 4, 1, 4 }, 3));
}
}手工推演 Lower Bound
数组 [1,2,2,2,5] 查找第一个 >=2 的位置:mid=2 满足条件,右边界收缩到 2;随后 mid=1 仍满足,再收缩到 1;最后检查位置 0 不满足,左边界移动到 1,答案确定。
对完整示例的 main 手工推导,预期依次输出 4、1、6。容量 6 时可分为 [3,2]、[2,4]、[1,4] 三天;容量 5 时按顺序至少需要四天,因此最小可行容量为 6。
6. 验证与排障
二分错误通常表现为死循环、越界或只在极端边界返回错误。可以建立表驱动测试,即列出输入与预期结果,逐项执行同一套断言。建议覆盖:
- 空数组、单元素和全部重复;
- target 小于最小值、大于最大值、刚好存在和落在间隙;
- Lower Bound 返回位置之前的值都小于目标,之后的值都大于等于目标;Upper Bound 对应
<=与>,两者之差等于目标出现次数; - 答案恰好位于上下界;
- 总重量超过
int时使用long的场景,以及feasible在边界两侧的单调性。
小规模输入还可以用顺序扫描作为边界查找的对照结果,用枚举容量和合法分组作为运力计算的对照。
若线上出现偶发错误,优先记录输入区间、最终 left/right 和可行性判断结果,而不是只打印“binary search failed”。
7. 容易踩的坑
- 将闭区间的
left <= right用于左闭右开数组模板,会在区间为空时仍尝试访问元素。 - 在本文向下取中点的写法中改成
left = mid,当right = left + 1时中点仍是left,区间无法缩小。 - 数据未排序或可行性不单调时,中点判断无法排除整段候选。
- 将任意等值位置当成第一个位置,或将返回的数组长度当作合法下标使用。
- 答案上界过小或累加溢出,会破坏初始区间覆盖答案的前提。
8. 总结
二分查找的本质,是在单调空间中维护一个不会丢失答案的搜索区间。
- 先确定区间语义,再写循环条件与边界更新。
- Lower Bound 比“找到任意相等值”更具通用性。
- 对答案二分还需保证区间覆盖答案、可行性判断正确,以及终止条件符合答案类型。