JAVAd的二分查找

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