商品价格已经从低到高排列。用户设置最低价格后,页面需要从第一个达到这个价格的商品开始展示。
从头逐个比较当然可行,但数组已经有序:看到中间价格仍然偏低,就能同时排除它左边的全部商品。这种利用顺序、反复缩小范围的查找方式,叫作二分查找。
这一篇只实现一个明确目标:在非递减数组中,找到第一个大于或等于目标值的位置。 非递减允许相邻元素相等。掌握这个边界以后,查找指定数字、寻找插入位置都能在它的基础上完成。
本文使用 Java 17+。系列目录 · 上一篇:双指针与滑动窗口 · 下一篇:递归与归并排序
一、先约定返回值
假设输入数组为:
下标: 0 1 2 3 4数值: 1 3 3 5 8我们把方法命名为 lowerBound。它返回一个下标,规则如下:
| 目标值 | 返回值 | 含义 |
|---|---|---|
3 | 1 | 第一个不小于 3 的元素在下标 1 |
4 | 3 | 没有 4,但下标 3 的 5 已经达到要求 |
0 | 0 | 所有元素都达到要求 |
9 | 5 | 没有元素达到要求,返回数组长度 |
返回数组长度 n,表示边界在所有元素之后。它是一个合法的边界位置,但不是可以读取的数组下标。空数组也按这条规则返回 0。
这里已经区分了两个问题:lowerBound 找的是分界位置;“目标值是否存在”还需要检查该位置的元素是否恰好等于目标。
二、为什么能一次排除一半
看中间位置 mid,只会遇到两种情况。
如果 values[mid] < target,因为数组有序,mid 左侧的数也都小于目标。这一段不可能提供答案,下一轮从 mid + 1 开始。
如果 values[mid] >= target,中间位置已经满足条件,但它左边可能还有更早的合格元素。我们保留这个边界,继续向左缩小范围。
特别是在数组含有重复值时,遇到相等就立即返回,只能得到某一次命中的位置,不能保证它是第一次出现的位置。
这套排除逻辑依赖排序前提。比如数组 [8, 1, 3],中间值 1 偏小,却不能推出左边的 8 也偏小;直接套用二分会丢掉可能的答案。
三、固定使用半开区间
本篇统一用 [left, right) 表示还要检查的元素范围:包含左端,不包含右端。
开始时 left = 0、right = values.length,刚好覆盖整个数组。每次循环保持两个事实:
- 下标小于
left的元素,已经确定小于目标值。 - 下标大于或等于
right的元素,已经确定大于或等于目标值。
这两条在每一轮都成立的事实,叫作循环不变量。它们让边界更新有依据,也能解释循环结束后的结果。
下面是完整源码中的两个方法,省略了外层类和演示用的 main:
public static int lowerBound(int[] values, int target) { if (values == null) { throw new IllegalArgumentException("values must not be null"); } 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;}
public static int firstIndexOf(int[] values, int target) { int index = lowerBound(values, target); return index < values.length && values[index] == target ? index : -1;}left + (right - left) / 2 避免先计算 left + right 导致整数溢出。在这里,两个端点都是非负下标或数组末尾边界。
为什么右边写 right = mid,而不是 mid - 1?因为 right 本来就是不包含的端点。我们把 mid 及右侧归入“已经确定合格”的部分,下一轮只检查它左侧有没有更早的边界。
当 left == right 时,没有待检查的元素。这个位置左边全部不合格,右边全部合格,所以它就是答案。若所有元素都小于目标,两个端点最终都会走到 n。
四、手动追踪一次重复值查找
在 [1, 3, 3, 5, 8] 中查找第一个不小于 3 的位置:
| 轮次 | left | right | mid 与数值 | 本轮更新 |
|---|---|---|---|---|
| 1 | 0 | 5 | mid = 2,值为 3 | 合格,令 right = 2 |
| 2 | 0 | 2 | mid = 1,值为 3 | 合格,令 right = 1 |
| 3 | 0 | 1 | mid = 0,值为 1 | 偏小,令 left = 1 |
| 结束 | 1 | 1 | 区间为空 | 返回 1 |
第一次已经看到了 3,却还要继续,正是为了找到前面的另一个 3。
每一轮也必须让范围变小。当只有一个元素时,mid 等于 left。若该元素偏小,写成 left = mid 就不会移动,程序会一直重复这一轮。因此这里必须使用 mid + 1。
五、运行与边界检查
下载完整 BinarySearch.java,在文件所在目录运行:
javac -encoding UTF-8 BinarySearch.javajava BinarySearch预期输出:
135-1四行分别是查找边界 3、4、9,以及查找数字 4 的首次出现位置。也可以下载整个系列的示例代码。
继续把下面几组输入放进 main 验证:
| 输入 | 调用 | 预期 |
|---|---|---|
[] | lowerBound(values, 3) | 0 |
[3] | lowerBound(values, 3) | 0 |
[3] | lowerBound(values, 4) | 1 |
[2, 2, 2] | firstIndexOf(values, 2) | 0 |
[1, 5] | firstIndexOf(values, 3) | -1 |
firstIndexOf 先判断 index < values.length,再读取元素。Java 的 && 会短路:左侧不成立时不再计算右侧,因此能避开末尾边界的越界访问。
方法拒绝 null,但接受长度为 0 的数组。调用方要保证排序前提;本方法没有在每次查询前重新扫描检查顺序。
另一个常见错误是混用不同的区间约定。这里的 right 可以等于数组长度,循环条件就必须配合使用 left < right。例如输入 [3]、目标为 4,第一轮结束后两端都为 1;如果改成 left <= right,下一轮就会试图读取不存在的下标 1。
负数和很大的目标值本身不会破坏算法,因为判断依赖大小比较,没有计算 target - values[mid]。写出一个版本后,始终沿用同一套端点含义,比同时背几种边界更新公式更容易检查正确性。
六、复杂度包含哪些成本
对非空数组,每轮把待检查范围缩小到大约一半,最多进行 O(log n) 轮。数组通过下标读取元素是常数时间,因此整个查询的时间复杂度为 O(log n),额外空间为 O(1)。空数组直接返回,耗时为常数。
如果数据原本没有排序,不能只报告二分的成本。先用 O(n log n) 的比较排序,再执行一次二分,总成本仍由排序主导。只查一次时,直接进行 O(n) 的线性扫描可能更合适。
有序数据被反复查询时,二分的优势更容易体现。若输入规模为 n、执行 q 次查询,先排序再二分的典型成本是 O(n log n + q log n),而每次从头扫描是 O(qn)。
这些分析还假设能够常数时间访问中间位置。不能仅因为链表也有顺序,就把数组二分的时间结论直接搬过去。
七、练习:统计目标值出现了几次
已经会找第一个 >= target 的位置,再实现一个 upperBound:找第一个 > target 的位置。两个边界相减,就是出现次数。
在 [1, 3, 3, 3, 5] 中,目标 3 的左右边界应为 1 和 4,出现次数为 3;目标 2 的两个边界都为 1,出现次数为 0。
提示:继续保留半开区间,只调整哪些值应当被排除到左侧。不要用 lowerBound(target + 1) 代替整个实现,否则当目标为 Integer.MAX_VALUE 时,加一会溢出。
写完后,用空数组、全相等数组和目标不存在的情况检查。你应该能解释每次移动边界的理由,再进入下一篇:递归与归并排序。
If this article helped you, please share it with others!
Some information may be outdated






