二分查找的工业级实现：溢出、边界与泛型适配的细节

一、看似简单的二分查找，为什么 Java 标准库也有过重大 Bug

二分的逻辑任何一个算法入门者都能背出来：取中间值，和目标比较，缩小搜索区间，重复直到找到或区间为空。这么简单的算法，能有什么问题？事实上，Java 标准库中Arrays.binarySearch的早期版本存在一个整数溢出 bug。int mid = (low + high) / 2这行代码，当low + high超过Integer.MAX_VALUE时，结果是一个负数，导致数组越界。这个 bug 在 JDK 6 中被修复，修复方式是把(low + high) / 2改成low + (high - low) / 2。

这就是二分查找的典型面貌：逻辑极其简单，但细节隐藏着多个陷阱。每一步都能写出正确代码的人，比能讲出二分原理的人少得多。

flowchart TD A["初始化: low = 0, high = n-1"] --> B{"low <= high ?"} B -->|否| C["返回 -1，未找到"] B -->|是| D["mid = low + (high-low)/2"] D --> E{"arr[mid] == target ?"} E -->|是| F["返回 mid"] E -->|<| G["low = mid + 1"] E -->|>| H["high = mid - 1"] G --> B H --> B

二、三个最常见的错误

错误一：溢出。(low + high) / 2在 int 范围内溢出。如果 low 和 high 都是 10 亿左右，相加后超过 21 亿（Integer.MAX_VALUE），结果变为负数。正确写法是low + (high - low) / 2或(low + high) >>> 1（无符号右移）。

错误二：边界条件。循环条件是low <= high还是low < high？答案是取决于查找区间的定义。如果区间是左闭右闭的[low, high]，当 low == high 时区间中还有一个元素需要检查，所以条件应该是low <= high。如果区间是左闭右开的[low, high)，low == high 时区间为空，条件应该是low < high。

错误三：更新方向。找到 mid 后，low = mid + 1和high = mid - 1中的 +1 和 -1 也很关键。如果不加这 1，当区间缩小到只有两个元素时，mid 始终等于 low，区间永远不会缩小，形成死循环。

这三个错误本质上都源于同一个问题：二分查找的核心是"不变量"——每次循环开始时，目标值一定在[low, high]这个区间内。只要维持好这个不变量，所有边界写法都能推导出来。

三、带泛型适配的生产级实现

/** * 生产级二分查找实现 * * 设计要点： * 1. 防止整数溢出：使用 low + (high - low) / 2 * 2. 支持泛型：通过 Comparator 适配任意类型 * 3. 支持左边界搜索：查找第一个等于 target 的位置 * 4. 递归版本已移除：生产环境不适合递归（栈溢出的隐患） */ public class BinarySearchUtil { /** * 基础版：在有序数组中查找 target，返回索引，不存在返回 -1 * * 适用场景：简单的存在性查找 */ public static <T> int search(T[] array, T target, Comparator<T> comparator) { // 防御性校验：空数组直接返回 -1 if (array == null || array.length == 0) { return -1; } int low = 0; int high = array.length - 1; // 左闭右闭区间 while (low <= high) { // 防溢出写法：low + (high - low) / 2 // 这个写法的正确性：low 和 high 都不会溢出， // high - low 也不会溢出（因为 high >= low） int mid = low + (high - low) / 2; int cmp = comparator.compare(array[mid], target); if (cmp == 0) { return mid; } else if (cmp < 0) { // array[mid] < target → 目标在右边 low = mid + 1; } else { // array[mid] > target → 目标在左边 high = mid - 1; } } return -1; // 未找到 } /** * 进阶版：查找第一个大于等于 target 的索引（lower_bound） * * 适用场景：插入位置查找、范围查询的下界 * 比如在 [1,2,2,2,3] 中找 2 的位置，返回 1（第一个 2） */ public static <T> int lowerBound(T[] array, T target, Comparator<T> comparator) { if (array == null || array.length == 0) { return -1; } int low = 0; int high = array.length - 1; int result = -1; // 记录最后一次等于 target 的位置 while (low <= high) { int mid = low + (high - low) / 2; int cmp = comparator.compare(array[mid], target); if (cmp >= 0) { // array[mid] >= target // 可能与 target 相等，记录位置后继续在左边搜索 // 为什么要继续搜左边？因为左边可能还有相等的元素 if (cmp == 0) { result = mid; } high = mid - 1; } else { // array[mid] < target → 目标在右边 low = mid + 1; } } return result; } /** * 进阶版：查找最后一个小于等于 target 的索引（upper_bound-1） * * 适用场景：范围查询的上界 * 比如在 [1,2,2,2,3] 中找 2 的最后一个位置，返回 3 */ public static <T> int upperBound(T[] array, T target, Comparator<T> comparator) { if (array == null || array.length == 0) { return -1; } int low = 0; int high = array.length - 1; int result = -1; while (low <= high) { int mid = low + (high - low) / 2; int cmp = comparator.compare(array[mid], target); if (cmp <= 0) { // array[mid] <= target if (cmp == 0) { result = mid; } low = mid + 1; // 继续在右边搜索 } else { high = mid - 1; } } return result; } }

lowerBound和upperBound是两个更高频的使用模式。普通的search只能回答"target 在不在数组里"，而lowerBound能回答"target 的第一个位置在哪"，upperBound能回答"target 的最后一个位置在哪"。前者用于存在性判断，后者用于范围统计——如果要统计 target 出现的次数，只需要upperBound - lowerBound + 1。

四、泛型版本与非泛型版本的差异

泛型版本通过Comparator解耦了比较逻辑，适用于任何类型。但有一个陷阱：Comparator.compare返回的是 int，而 int 的比较使用的是cmp == 0，而不是array[mid].equals(target)。这两个操作在某些类型（如BigDecimal）中的行为可能不一致——compareTo认为1.0和1.00相等，但equals认为它们不相等。如果二分查找的数组中使用的是compareTo定义的顺序，比较时也应该用compareTo，否则会出现逻辑矛盾。

对于基本类型的数组（int[]），使用泛型版本有装箱拆箱的开销，查询频率极高时这点开销会累积成可观的性能差距。所以在 JDK 的Arrays.binarySearch中，每种基本类型都有独立的特化实现，没有使用泛型。

五、总结

二分查找的核心逻辑确实不复杂——但前提是你得把不变量想清楚。溢出问题在 64 位索引为主流的今天出现概率降低了，但边界条件和搜索方向仍然是常见的错误来源。工程实现上，泛型适配和 lower_bound/upper_bound 的变体是二分查找在实际业务中的主要使用形态。写完代码后用几个精心设计的测试用例（空数组、单元素、重复元素、溢出边界值）验证一下，很多时候能发现自以为写对了但实际有问题的边界逻辑。