JAVAd的二分查找

一、核心概念
二分查找也叫折半查找，是有序序列专属的查找算法。每次把查找范围缩小一半，查找效率远高于逐个遍历。
- 时间复杂度：O(\log n)
- 适用场景：仅支持有序、可随机访问的数据（如数组），不适合链表。
二、基础前提
1. 数据必须提前升序/降序排列，无序数据无法使用。
2. 依靠下标快速定位中间元素，顺序访问结构不适用。
三、执行流程（以升序为例）
1. 划定范围：设定左边界、右边界，初始分别指向序列第一个、最后一个元素。
2. 取中间位置：计算左右边界的中间位置。
3. 对比中间元素与目标值：
- 相等：查找成功，结束。
- 中间值 < 目标值：目标在右半区，更新左边界，舍弃左半部分。
- 中间值 > 目标值：目标在左半区，更新右边界，舍弃右半部分。
4. 循环重复上述步骤，直到找到目标；若左边界超过右边界，说明序列中无该元素，查找失败。
四、关键细节与易错点
1. 边界条件
循环判断必须使用「左边界 ≤ 右边界」，否则会漏掉最后一个待检查元素。
每次更新边界时，不能直接赋值为中间位置，必须在中间位置基础上±1，否则会陷入死循环。
2. 整数溢出问题
直接用「左+右」计算中间位置，数值过大时会出现整数溢出。
优化方式：用 左 + (右-左)÷2 计算中间位置，规避溢出风险。
五、Java 内置方法规则
Java 工具类自带二分查找方法，使用前同样要求数组有序：
- 找到目标：返回元素对应的下标。
- 未找到目标：返回负数，规则为 -(插入位置)-1 （插入位置指该元素有序存入数组时的位置）。
六、拓展：存在重复元素的场景
当序列中有多个相同目标值时，可改造算法查找边界：
1. 左边界：找到第一个等于目标值的元素。
遇到大于等于目标值的元素，就收缩右边界，最终校验左边界是否为目标值。
2. 右边界：找到最后一个等于目标值的元素。
遇到小于等于目标值的元素，就扩张左边界，最终校验右边界是否为目标值。
七、两种实现方式对比
1. 循环实现：主流用法，无栈溢出风险，执行效率更高。
2. 递归实现：逻辑易懂，依靠递归缩小区间；数据量极大时可能出现栈溢出，一般不推荐优先使用。