Collections.binarySearch查找效率之探讨：二分法查找的优势分析

二分法查找的核心优势是将搜索次数压缩至对数级，100 万个元素最多仅需 20 次比较；它要求数据有序且支持随机访问，故适用于 ArrayList 而不适用于 LinkedList；使用自定义 Comparator 时必须保持排序与查找逻辑一致；查不到时返回的负值可直接换算为插入位置，便于维护动态有序列表。

二分法查找的核心优势在于它能把搜索次数压缩到对数级，100 万个元素最多只需 20 次比较，远快于线性扫描。

只对有序随机访问列表有效

binarySearch 要求数据必须已排序，且底层必须支持 O(1) 时间定位中间元素——所以 ArrayList 可以，LinkedList 不行。后者每次取 mid 都得从头遍历，时间复杂度退化成 O(n)，二分就失去了意义。

• 调用前务必确认 list 已按相同规则排好序
• 若用自定义 Comparator 排序，binarySearch 时也必须传同一个实例
• 升序排完却用降序 Comparator 去查，结果等同于在乱序数据上硬套逻辑，毫无可靠性

效率对比非常直观

线性查找平均要检查一半元素，最坏情况得比对全部 n 个；二分查找每次砍掉一半范围，10⁶ 元素最多 20 次，10⁹ 元素也才约 30 次。这种差距在真实业务中直接体现为响应延迟的大幅下降。

• 数组长度每翻一倍，二分查找最多只多一次比较
• 而线性查找的最坏耗时会同步翻倍
• 当数据量超过几万，二分的优势就非常明显

查不到也能立刻知道插哪

返回负值不是随便设计的：-4 表示目标应插入索引 3 的位置。这个 insertionIndex 可直接用于 list.add(-result - 1, target)，无需额外遍历或重写逻辑，特别适合维护动态有序缓存或构建轻量级优先队列。

• 避免重复计算插入位置，减少出错可能
• 配合 sort + binarySearch + add，能稳定维持列表有序性
• 适用于读多写少、需保持局部有序的场景

不复杂但容易忽略细节