Java二分查找技巧与原理详解

Java的二分查找（Arrays.binarySearch）并非“万能搜索工具”，其正确性严格依赖数组已按升序（或指定Comparator一致的顺序）预先排序这一前提；未排序、降序但未配对Comparator、类型不匹配或误读负数返回值（它编码插入位置而非简单“未找到”）等常见误区，都会导致结果不可靠甚至逻辑错误——真正的问题往往不出在查找本身，而在于调用前缺失的排序准备或对API契约的误解。

Arrays.binarySearch 为什么搜不到明明存在的元素

因为 Arrays.binarySearch 只在**已排序数组**上保证正确性；未排序时返回值无意义，可能为负数、0，甚至“碰巧”对上某个索引——但这纯属巧合，不可依赖。

• 常见错误现象：Arrays.binarySearch(arr, 42) 返回 -1，但 Arrays.asList(arr).contains(42) 是 true
• 根本原因：二分查找每次比较后直接舍弃一半区间，前提是数组单调（升序/降序），否则“舍弃”会漏掉目标
• 使用场景仅限：确认数组已按自然序或指定 Comparator 排好序，且后续无写入干扰排序状态
• 别试图“先查再排”——排序是 O(n log n)，查是 O(log n)，合起来不如线性扫描 O(n) 来得实在

升序 vs 降序数组，binarySearch 能不能直接用

默认只支持升序；传入降序数组会导致结果完全不可预测，Arrays.binarySearch 不做任何顺序校验。

• 升序安全：用 Arrays.binarySearch(arr, key) 或 Arrays.binarySearch(arr, key, comparator)，其中 comparator 必须与排序时用的一致
• 降序必须显式传 Comparator：比如 Arrays.binarySearch(arr, key, Collections.reverseOrder())，且前提是数组真用这个 comparator 排过序
• 参数差异关键点：comparator 不仅影响比较逻辑，还决定“中点选择”后的分支方向——错配就等同于乱跳
• 性能无额外开销，但兼容性极差：JDK 8+ 才支持 Comparator 版本的 binarySearch 对基本类型数组无效（只能用包装类数组）

返回值负数到底代表什么

负数不是“没找到”的简单标记，而是带位置信息的插入点编码，必须用公式还原。

• 若返回值 ≥ 0：就是目标元素的索引，可直接用
• 若返回值 -(return_value) - 1，例如返回 -5，表示应插入到索引 4
• 容易踩的坑：直接判断 result 就认为“不存在”，却忽略插入点可用于维护有序结构（如实现 TreeSet 风格的插入逻辑）
• 不要手写 if (result ——这是错的，必须用原值参与运算

基本类型数组和对象数组的差异陷阱

基本类型数组（int[]、double[] 等）不支持自定义 Comparator，且 null 值直接抛 NullPointerException。

• 对象数组（Integer[]、String[]）才能用 Comparator 版本，也才能处理 null（取决于 comparator 实现）
• 基本类型数组调用 binarySearch 时，key 类型必须严格匹配：用 int 查 int[]，不能用 long 或 Integer（会触发自动装箱，查的是对象数组）
• 性能影响：基本类型版本是纯数组下标操作，无对象开销；对象版本涉及引用比较、可能触发 GC，但差别通常可忽略
• 兼容性注意：Android API 26+ 才完整支持所有重载，低版本对 double[] 等某些类型可能缺失方法签名

排序这件事没法偷懒——binarySearch 的契约里，“已排序”是前提条件，不是可选优化。很多人卡在返回负数上反复调试，其实问题早发生在调用前那行没写的 Arrays.sort()。

终于介绍完啦！小伙伴们，这篇关于《Java二分查找技巧与原理详解》的介绍应该让你收获多多了吧！欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识，快来关注吧！