mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
1976 words
5 minutes
算法入门(四):二分查找与边界
2026-10-21

商品价格已经从低到高排列。用户设置最低价格后,页面需要从第一个达到这个价格的商品开始展示。

从头逐个比较当然可行,但数组已经有序:看到中间价格仍然偏低,就能同时排除它左边的全部商品。这种利用顺序、反复缩小范围的查找方式,叫作二分查找。

这一篇只实现一个明确目标:在非递减数组中,找到第一个大于或等于目标值的位置。 非递减允许相邻元素相等。掌握这个边界以后,查找指定数字、寻找插入位置都能在它的基础上完成。

本文使用 Java 17+。系列目录 · 上一篇:双指针与滑动窗口 · 下一篇:递归与归并排序

一、先约定返回值#

假设输入数组为:

下标: 0 1 2 3 4
数值: 1 3 3 5 8

我们把方法命名为 lowerBound。它返回一个下标,规则如下:

目标值返回值含义
31第一个不小于 3 的元素在下标 1
43没有 4,但下标 3 的 5 已经达到要求
00所有元素都达到要求
95没有元素达到要求,返回数组长度

返回数组长度 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 的位置:

轮次leftrightmid 与数值本轮更新
105mid = 2,值为 3合格,令 right = 2
202mid = 1,值为 3合格,令 right = 1
301mid = 0,值为 1偏小,令 left = 1
结束11区间为空返回 1

第一次已经看到了 3,却还要继续,正是为了找到前面的另一个 3。

每一轮也必须让范围变小。当只有一个元素时,mid 等于 left。若该元素偏小,写成 left = mid 就不会移动,程序会一直重复这一轮。因此这里必须使用 mid + 1。

五、运行与边界检查#

下载完整 BinarySearch.java,在文件所在目录运行:

javac -encoding UTF-8 BinarySearch.java
java BinarySearch

预期输出:

1
3
5
-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 时,加一会溢出。

写完后,用空数组、全相等数组和目标不存在的情况检查。你应该能解释每次移动边界的理由,再进入下一篇:递归与归并排序。

Share

If this article helped you, please share it with others!

算法入门(四):二分查找与边界
https://mizuki.mysqil.com/posts/algorithm-04-binary-search/
Author
梦幻晨风
Published at
2026-10-21
License
CC BY-NC-SA 4.0

Some information may be outdated

Table of Contents