二分查找比线性查找快得多，因其时间复杂度为O(log n)，10⁶元素最多20次比较，而线性查找最坏需n次、平均n/2次；前提须有序、随机访问且Comparator一致，并支持插入点定位。

二分法查找的效率优势，核心在于它把查找次数压到了对数级——100 万个元素最多比 20 次，而不是线性扫描平均要试 50 万次。

为什么比线性查找快得多

线性查找从头到尾逐个比对，最坏情况要检查全部 n 个元素，时间复杂度 O(n)；而 binarySearch 每次比较后直接砍掉一半搜索范围，最多只需 ⌊log₂n⌋ + 1 次比较：

• 10⁶ 元素 → 最多 20 次比较
• 10⁹ 元素 → 最多 30 次比较
• 哪怕数据翻十倍，比较次数只增加约 3～4 次

前提条件必须满足

高效不是无代价的，binarySearch 只在严格条件下才能发挥优势：

• 列表必须已按升序排序（升序是默认约定，降序需额外处理）
• 必须是支持随机访问的 List，比如 ArrayList；LinkedList 不适用，因为取中间元素要遍历，退化成 O(n)
• 排序和查找用的 Comparator 必须完全一致——排序时按年龄升序，查找时就不能用姓名或降序比较器

返回值自带插入逻辑

查不到时返回 -(insertionIndex) - 1，这个设计不只是标记“没找到”，而是直接给出维持有序所需的插入位置：

• 返回 -4 → 应插入索引 3 的位置
• 配合 list.add(-result - 1, target)，可无缝插入并保持有序
• 适合构建动态有序缓存、优先队列等场景，省去二次定位开销

实际使用中的关键细节

很多问题不是算法本身慢，而是用法偏差导致效果打折：

• 别跳过排序步骤：先 Collections.sort(list, comparator)，再 binarySearch
• 自定义对象查找时，Comparator 的 compare 方法必须满足一致性（比如不能对同一对对象返回不同结果）
• 避免在循环中反复调用 binarySearch 查找不同目标——如果目标集固定，考虑提前建哈希表；但若数据静态+查询频繁，binarySearch 仍是轻量高性价比选择