二分查找的原理是什么？为什么是 O(log n)？

简化版

二分查找在有序数组里找目标值:每次取中间元素和目标比较,相等就找到、目标小就往左半找、目标大就往右半找,一次比较排除掉一半元素。因为每次搜索范围减半,n 个元素最多比较 log₂n 次,所以是 O(log n)。前提是数组必须有序。注意 mid = lo + (hi-lo)/2 防止 lo+hi 整数溢出。

详细版

int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;      // 闭区间 [lo, hi]
    while (lo <= hi) {                    // 区间非空
        int mid = lo + (hi - lo) / 2;    // 防溢出，等价于 (lo+hi)/2
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1; // 目标在右半
        else hi = mid - 1;                        // 目标在左半
    }
    return -1;                            // 没找到
}

前提:数组有序(这里假设升序)。
每一步:比较 a[mid] 和 target,排除掉一半。
收缩:目标更大 → lo = mid+1;更小 → hi = mid-1;相等 → 返回。
退出:lo > hi 时区间为空,没找到。

完整版教学

一、核心思想:利用有序性,每次排除一半

二分查找的威力来自「有序」这个前提。数组有序意味着:拿目标和中间元素一比,就能确定目标只可能在左半或右半——另一半可以整个丢弃。

a[mid] == target:正好找到。
a[mid] < target:因为有序,mid 及它左边的都 ≤ a[mid] < target,目标只可能在右半,lo = mid+1。
a[mid] > target:同理目标在左半,hi = mid-1。

每一次比较都把搜索范围砍掉一半,这就是「二分」的含义,也是它高效的根源。

二、为什么是 O(log n)

设数组有 n 个元素。每比较一次,范围减半:n → n/2 → n/4 → … → 1。需要多少次才能从 n 缩到 1?就是「n 连续除以 2 多少次到 1」,即 log₂n 次。所以最坏比较 O(log n) 次,时间复杂度 O(log n)。

直观感受:10 亿个有序元素,线性查找最坏要 10 亿次;二分只要约 30 次(2³⁰ ≈ 10 亿)。这就是对数复杂度的威力——数据翻倍,只多比较一次。

三、防溢出:mid 的正确写法

mid = (lo + hi) / 2 有个隐患:当 lo 和 hi 都很大时,lo + hi 可能超出 int 范围而溢出变成负数,导致下标错误甚至崩溃。正确写法是:

int mid = lo + (hi - lo) / 2;

hi - lo 不会溢出(两个正数相减),加上 lo 得到的还是 [lo, hi] 中点,结果和 (lo+hi)/2 相同但安全。这是二分的一个经典细节,面试写代码时要注意。

四、闭区间写法的三个要点

上面的写法用闭区间 [lo, hi](两端都包含),它的三个细节必须配套:

初始 hi = n-1:因为区间包含 hi,最后一个有效下标是 n-1。
循环条件 lo <= hi:当 lo == hi 时区间还有一个元素,要继续检查;lo > hi 才是空区间。
收缩 mid±1:因为 a[mid] 已经比较过、可以排除,所以下次区间从 mid+1 或 mid-1 开始,不重复检查 mid。

这三点互相呼应,是二分不出错、不死循环的关键(边界处理见专题)。

五、二分查找的前提和局限

必须有序:无序数组不能二分(先排序 O(n log n) 就不如直接遍历 O(n) 了,除非多次查询)。
随机访问:需要 O(1) 按下标访问,所以适合数组;链表不能高效二分(没有随机访问,找中点要 O(n))。
静态或少改动:频繁插入删除会破坏有序性,维护成本高;这种场景用平衡 BST 或跳表更好。

六、二分的应用远不止「找一个数」

基础二分是「在有序数组里找某个值」,但二分的思想适用面广得多:

找边界:第一个/最后一个等于 target 的位置(lower/upper bound)。
搜索插入位置、旋转数组查找、寻找峰值。
二分答案:在「答案的取值范围」上二分(求平方根、最小化最大值等),只要答案有单调性就能用。

核心都是「利用单调性,每次排除一半可能」——这才是二分的精髓,而不只是「找一个数」。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：搜索区间始终包含所有尚未排除的目标位置。

对应的状态推进是：比较 a[mid] 与 target 后，利用有序性一次排除不可能的一半。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。最多比较 floor(log₂n)+1 次，因此 O(log n)。

带数字走一遍：长度 16 的有序数组最多约 5 次比较即可确定找到或不存在。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	要求随机访问且判定方向单调；普通链表不适合
时间复杂度	O(log n)
额外空间	O(1)
关键边界	mid 用 lo+(hi-lo)/2 防加法溢出；区间定义决定 lo/hi 更新
替代方案	无序数据用哈希或先排序，频繁动态更新可用平衡树

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“要求随机访问且判定方向单调；普通链表不适合”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“最多比较 floor(log₂n)+1 次，因此 O(log n)”。
误区：重复值和边界值不会改变代码。 mid 用 lo+(hi-lo)/2 防加法溢出；区间定义决定 lo/hi 更新。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“搜索区间始终包含所有尚未排除的目标位置”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“长度 16 的有序数组最多约 5 次比较即可确定找到或不存在”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“无序数据用哈希或先排序，频繁动态更新可用平衡树”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

二分查找在有序数组上,每次拿中间元素比较、排除一半(目标小往左、大往右、相等命中),所以 O(log n)(n 连续减半 log₂n 次到 1,10 亿只需约 30 次)。写法要点:mid = lo + (hi-lo)/2 防溢出;闭区间 [lo,hi] 配套「hi=n-1、while lo<=hi、收缩 mid±1」。前提是有序 + 可随机访问(适合数组)。精髓是「利用单调性排除一半」,可延伸到找边界、旋转数组、二分答案等。

简化版

详细版