Arrays.binarySearch的核心是二分查找，仅适用于已排序数组，时间复杂度为O(log n)；因每次比较将搜索范围减半，k次后剩余n/2ᵏ个元素，故最多log₂n次即可定位；未找到时返回-(insertionPoint+1)，兼具失败标识与插入位置提示。

Arrays.binarySearch 的核心就是二分查找，它只在**已排序的数组**中有效，时间复杂度稳定为 O(log n)。

为什么是 O(log n)？

因为每次比较后，搜索范围都精确砍掉一半：

• 初始范围是整个数组，长度为 n
• 第一次比较后，最多剩 n/2 个元素
• 第二次比较后，最多剩 n/4 个元素
• ……
• 第 k 次后，最多剩 n / 2 个元素

当范围缩小到 1 时，即 n / 2^k = 1，解得 k = log₂n。所以最多比较 log₂n 次，这就是 O(log n) 的由来。

和线性查找对比更明显

面对 100 万个元素的数组：

• 线性查找最坏要检查 100 万次
• 二分查找最多只需约 log₂(10⁶) ≈ 20 次

实际实现中的关键细节

Java 的 Arrays.binarySearch 使用的是**迭代版**，避免递归调用开销：

• 用 low 和 high 控制当前搜索区间
• 中间索引用 (low + high) >>> 1 计算，防止整数溢出且保证非负右移
• 未找到时返回 -(insertionPoint + 1)，既标识失败，又提供插入位置信息

前提条件不能忽略

O(log n) 的高效性完全依赖两个前提：

• 数组必须是升序（或降序，但需统一且 API 默认按升序处理）
• 数据基本静态——频繁插入/删除会破坏有序性，反而让整体性能下降