数据结构与算法 / 系统课时
二分查找
二分查找
二分查找利用数组的非递减顺序,比较中点后排除一侧。本课先实现“返回任意匹配位置”,再用另一套区间约定实现“第一个不小于目标的位置”。两者可以处理相同输入,但输出契约不同。
学习目标
- 按不变式核对闭区间的初始化、收缩和退出。
- 区分任一匹配、首次匹配和插入位置。
- 避免中点或比较溢出,验证空数组、重复键及首尾。
闭区间:找到任一匹配
数组必须按非递减顺序排列。调用者负责维持这个前提,本例不每次重新扫描数组验证。候选区间初始为 [0,length-1]。在每轮开始时,若目标存在,当前区间仍包含某个匹配位置。若中点值小于目标,左侧连同中点不可能匹配,改令 left=middle+1;若较大,改令 right=middle-1。相等可立即返回。循环结束时候选区间为空,故返回 -1。 MIT 二分查找递推 Java Arrays 二分查找前提
用 left+(right-left)/2 计算中点,避免把两个大下标直接相加。比较整数时使用 Integer.compare 或关系运算,不能用中点值减目标作为大小比较,以免极端整数相减溢出。每次未命中后至多留下原候选数的一半, 时最多探测 个中点,最坏时间为 。迭代版辅助空间为 ,空数组不探测。 Java Integer.compare
半开区间:找到插入位置
lowerBound 返回第一个大于或等于目标的下标。如果所有元素都小于目标,返回 length。维护 [left,right),初始为 [0,length)。left 之前的值都小于目标,right 到末尾的值都不小于目标。中点小于目标时令 left=middle+1,否则令 right=middle,把中点归入右侧已知区域。两端相遇时就得到边界。要找第一次等于目标的位置,还须检查边界下标是否在数组内以及该值是否相等。
Java Arrays.binarySearch 也是“任一匹配”,存在重复键时不保证选中第一个。它未命中时编码插入位置,本课的 binarySearch 则统一返回 -1,两种失败返回不能互换。 Java Arrays.binarySearch 返回值
Java 17 实例
保存为 BinarySearchDemo.java,执行 javac -encoding UTF-8 --release 17 BinarySearchDemo.java 和 java BinarySearchDemo。闭区间追踪是可选调试输出,验证复杂度时关闭。
import java.util.Objects;
public class BinarySearchDemo {
public static int binarySearch(int[] values, int target, boolean trace) {
Objects.requireNonNull(values, "values");
int left = 0;
int right = values.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (trace) {
System.out.printf("[%d,%d] mid=%d value=%d%n", left, right, middle, values[middle]);
}
int comparison = Integer.compare(values[middle], target);
if (comparison == 0) {
return middle;
}
if (comparison < 0) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}
public static int lowerBound(int[] values, int target) {
Objects.requireNonNull(values, "values");
int left = 0;
int right = values.length;
while (left < right) {
int middle = left + (right - left) / 2;
if (values[middle] < target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}
public static int firstIndex(int[] values, int target) {
int at = lowerBound(values, target);
return at < values.length && values[at] == target ? at : -1;
}
public static void main(String[] args) {
int[] values = {3, 8, 12, 19, 27, 35, 46};
System.out.println("命中 27: " + binarySearch(values, 27, true));
System.out.println("查找 20: " + binarySearch(values, 20, false));
System.out.println("20 的插入位置: " + lowerBound(values, 20));
System.out.println("首次出现 2: " + firstIndex(new int[]{1, 2, 2, 2, 5}, 2));
}
}[0,6] mid=3 value=19
[4,6] mid=5 value=35
[4,4] mid=4 value=27
命中 27: 4
查找 20: -1
20 的插入位置: 4
首次出现 2: 1本课练习
测试小于所有元素、大于所有元素、空数组和重复极值。再实现 upperBound 返回第一个严格大于目标的下标,检查用它减去 lowerBound 能否得到出现次数。后续将进入选择算法,讨论如何在未排序数组中定位给定秩的元素。