Java二分查找前必须排序的原因

Java 的 `Arrays.binarySearch` 方法并非“万能查找工具”，其正确运行严格依赖数组已按升序排序这一硬性前提——未排序时结果完全不可预测，哪怕偶然命中也是巧合，绝非可靠行为；根本原因在于二分查找的逻辑基石是有序性带来的方向判断能力，乱序下中点比较会误导搜索路径，导致漏查、误判甚至返回毫无意义的负数索引；因此，任何使用前都必须显式调用匹配规则的 `Arrays.sort()`（原始类型用对应重载，自定义排序则需统一 `Comparator`），且严禁在排序后修改数组或混淆集合与数组操作——忽略这一契约，再精巧的代码也会在关键时刻悄然失效。

Java 的 Arrays.binarySearch 要求数组必须已升序排序，否则结果不可预测。这不是可选建议，而是方法契约的硬性前提——源码注释明确写有 “the array must be sorted”，违反时返回值无意义（可能为负数、0，甚至恰好“碰对”某个索引，但不具逻辑正确性）。

为什么必须先 sort？

二分查找依赖“有序性”做区间收缩：每次比较后能确定目标只可能在左半段或右半段。如果数组乱序，中点值无法提供方向信息，算法会跳过正确位置或陷入错误分支。

例如：int[] a = {5, 1, 8}; 未排序，查找 1：
– 第一次比较中点 a[1] == 1，看似命中，返回索引 1 —— 碰巧对了；
– 但查找 5 时，中点仍是 a[1]==1，因 5 > 1 去查右半段 {8}，最终返回 -2（插入点为 2，取反减 1），完全错误。

sort 的具体要求

• 必须使用与 binarySearch 相同的排序规则：若用 binarySearch(int[], key)，则需用 Arrays.sort(int[]) 升序排；
• 若用带 Comparator 的 binarySearch，则 sort 必须传入同一 Comparator；
• 原始类型数组（如 int[]）不能用 Comparable，所以不能混用泛型版本的 sort；
• 升序是唯一被保证的行为；降序排列后直接调 binarySearch，结果必定错误。

常见误用场景

• 对刚创建/读取的数组直接 binarySearch，忘了排序；
• 排序和查找之间修改了数组（如增删元素、赋新值），破坏有序性；
• 用 Collections.sort() 排 List，却调用 Arrays.binarySearch() 查数组（类型不匹配）；
• 认为“部分有序”或“几乎有序”可以省略 sort —— 不行，只要有一个逆序对，就可能出错。

安全使用的典型写法

以 int[] 为例：

int[] arr = {3, 7, 1, 9, 4};
Arrays.sort(arr); // 必须放在 binarySearch 前
int index = Arrays.binarySearch(arr, 4); // 此时 index >= 0 表示找到

对对象数组或自定义排序，确保 sort 和 binarySearch 使用同一个 Comparator 实例。

今天关于《Java二分查找前必须排序的原因》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！