有序列表二分查找技巧

本文深入剖析了Java中Collections.binarySearch在有序List上进行二分查找的关键要点与高频陷阱：它并非“开箱即用”的安全工具，而是严格依赖前提条件的精密操作——必须确保List已用同一Comparator升序排序、不可降序、不可含未排序元素，且仅适用于支持O(1)随机访问的List（如ArrayList）；返回值蕴含精确索引或标准化插入位置（-result - 1），但误用流式排序、null处理不当、类型不匹配、并发修改或在LinkedList上强行调用，都会导致结果失真或性能骤降；真正掌握它，不是学会调用方法，而是理解其零容错边界与背后的设计契约。

要用 Collections.binarySearch 在有序 List 中快速定位元素，关键不是“能不能用”，而是“怎么用才不翻车”。它本身不排序、不校验、不兜底——只在你确保一切就绪后，给出一个精准下标或插入点。

必须提前排好序，且只能是升序

binarySearch 不会帮你排序，也不会识别降序。哪怕只差一个元素位置错乱，结果就完全不可信。

• 对基本类型或 String/Integer 等，调用 Collections.sort(list) 即可
• 对自定义对象（如 Person），必须先用相同 Comparator 排序，再用同一个 Comparator 查找
• 千万别用 list.stream().sorted().collect(...) 后直接查——那是个新 List，原 list 还是乱的

查不到时返回负数，不是错误，是提示插入位置

返回值 ≥ 0 表示找到了，索引就是那个数；返回值

• 若返回 -4，说明应插入到索引 3 的位置（计算方式：-(-4) - 1 = 3）
• 这个插入位置一定在 [0, list.size()] 范围内：0 表示插最前，list.size() 表示插最后
• 想安全取插入点，别手算，直接写 -result - 1 就行

注意类型和容器的匹配边界

看似简单的方法，踩坑多在细节：

• 只能用于 List，不能传 ArrayList 的父类 Collection 或 Set
• 数组要用 Arrays.asList(arr) 包一层再查，但 arr 必须是包装类型（Integer[] 可以，int[] 不行）
• 列表含 null 时，Comparator 必须支持 null 比较，否则运行时报 NullPointerException
• 并发环境下，即使刚排完序，查的时候列表可能已被其他线程修改——结果不保证可靠

别在 LinkedList 上硬用

binarySearch 内部靠随机访问跳转，而 LinkedList 的 get(i) 是 O(n)。表面调用成功，实际退化成慢查找。

• 优先选 ArrayList 或 Arrays.asList 包装的固定列表
• 如果数据频繁增删又需二分，考虑换 TreeSet 或带索引的结构

以上就是《有序列表二分查找技巧》的详细内容，更多关于的资料请关注golang学习网公众号！