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

二分查找的工业级实现溢出、边界与泛型适配的细节一、看似简单的二分查找为什么 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, ComparatorT 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, ComparatorT 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, ComparatorT 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 的变体是二分查找在实际业务中的主要使用形态。写完代码后用几个精心设计的测试用例空数组、单元素、重复元素、溢出边界值验证一下很多时候能发现自以为写对了但实际有问题的边界逻辑。