二分查找为什么总写错？循环条件、mid、区间收缩该怎么配套？

简化版

二分写错,几乎都出在三个东西不配套:循环条件(<= 还是 <)、区间定义(闭区间 [lo,hi] 还是左闭右开 [lo,hi))、收缩方式(mid±1 还是 mid)。关键是认准一种区间定义,让三者互相配套,并保证每次循环搜索范围都在缩小(避免死循环)。推荐记牢两套固定模板(闭区间 + 左闭右开),别每次现推。

详细版

模板一:闭区间 [lo, hi](两端都取)

int lo = 0, hi = n - 1;          // 闭区间
while (lo <= hi) {                // 空区间是 lo > hi
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;  // 排除 mid，收 mid+1
    else hi = mid - 1;                        // 排除 mid，收 mid-1
}

模板二:左闭右开 [lo, hi)(hi 取不到)

int lo = 0, hi = n;              // 右开，hi 初始为 n
while (lo < hi) {                 // 空区间是 lo == hi
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid;                // 右开，hi = mid（不减 1）
}

配套规则:hi 初值、while 的 <=/<、收缩用 mid-1/mid,三者由「区间是否包含 hi」统一决定,不能混用。

完整版教学

一、为什么二分容易错

二分逻辑简单,但细节魔鬼:hi 初始是 n 还是 n-1?循环是 < 还是 <=?收缩是 mid 还是 mid-1?这些组合稍微搭错,就会漏掉边界元素、多算一位、或死循环。根源是很多人没有固定的「区间定义」,每次凭感觉写,自然容易错。解决办法只有一个:先明确区间定义,再让所有细节围绕它配套,并且用「循环不变量」来保证正确。

二、循环不变量:搜索区间的含义要始终一致

「循环不变量」是指:整个循环过程中,目标如果存在,一定在当前的搜索区间里。你要在写之前就定好区间的开闭,并让每一步都维持这个含义:

闭区间 [lo, hi]:lo 和 hi 都是「还需要检查」的位置。所以 hi 初值是 n-1(最后一个合法下标),空区间是 lo > hi(所以 while lo <= hi)。
左闭右开 [lo, hi):lo 需要检查,hi 是「第一个不检查」的位置。所以 hi 初值是 n,空区间是 lo == hi(所以 while lo < hi)。

定好了区间含义,hi 初值和循环条件就唯一确定了。

三、收缩方式必须和区间配套(关键)

收缩边界时,「排除掉的元素不能再进入区间,没排除的必须还在区间里」:

闭区间:a[mid] 已经比较过、要排除。所以下次区间不含 mid:lo = mid+1 或 hi = mid-1(都跳过 mid)。
左闭右开:排除 mid 时,左边界 lo = mid+1(跳过);右边界 hi = mid——因为右开,hi 本来就取不到,设成 mid 正好把 mid 排除在 [lo, mid) 之外。

混用是大坑:比如闭区间却写 hi = mid(没减 1),mid 会反复留在区间里,可能死循环;左闭右开却写 hi = mid-1,又会漏掉元素。所以收缩方式由区间定义决定,不能随意。

四、死循环是怎么来的

死循环的本质是:某次循环后搜索区间没有缩小。最经典的场景出现在「找边界」的变体里,当只剩两个元素、收缩用 lo = mid 而 mid 又取到 lo 时:

区间 [lo, hi] 只剩两个元素，mid = lo + (hi-lo)/2 = lo（下取整）
若收缩写 lo = mid  → lo 没变，死循环！

破解办法:如果某个分支要收缩成 lo = mid(而不是 mid+1),就必须让 mid 上取整:mid = lo + (hi - lo + 1) / 2,这样 mid 偏向 hi,lo = mid 才能真正前进。「lo = mid 配上取整,hi = mid 配下取整」 是防死循环的口诀。基础二分因为收缩都是 mid±1,天然不会死循环。

五、两套模板,记牢就好

与其每次现推,不如背下两套固定模板(上面详细版的两个),用的时候直接套:

精确查找一个值:两套都行,mid±1 收缩,return mid。
找左/右边界(lower/upper bound):推荐用左闭右开 [lo, hi) 模板,hi = mid 收缩,退出时 lo == hi 就是答案位置——这套模板处理边界最不容易错(见左/右边界专题)。

固定模板 + 理解循环不变量,二分就从「玄学」变成「套路」。

六、检查清单:写完二分自问三点

写完一个二分,按这三点自查,基本能避开所有坑:

区间定义是什么?(闭 [lo,hi] 还是左闭右开 [lo,hi))
循环条件、hi 初值、收缩方式是否都和区间定义配套?
每一步区间是否都在缩小?(尤其 lo=mid/hi=mid 的分支,mid 取整方向对不对)

这三项必须一起验证，而不是单独看某一行。最可靠的办法是给 lo、hi 和答案候选写出区间断言，再用长度为 1、2 的数组手推；只要某个分支不能让区间严格缩小，就可能死循环。

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

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：循环前后搜索区间的数学含义必须一致，答案从不被错误排除。

对应的状态推进是：闭区间用 lo<=hi 和 mid±1；左闭右开用 lo<hi 和 hi=mid。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

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

复杂度不能只背一个符号。每轮区间严格缩小，故最多 O(log n) 轮。

带数字走一遍：[0,1] 上若 mid 向下取整却写 lo=mid，会在 lo=0、hi=1 时死循环。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	所有二分变体都必须先写清区间与谓词
时间复杂度	O(log n)
额外空间	O(1)
关键边界	更新到 mid 时要确认 mid 是否仍可能是答案，并选择对应取整方向
替代方案	可统一采用 lower_bound 风格减少模板数量

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

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

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

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“所有二分变体都必须先写清区间与谓词”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“每轮区间严格缩小，故最多 O(log n) 轮”。
误区：重复值和边界值不会改变代码。 更新到 mid 时要确认 mid 是否仍可能是答案，并选择对应取整方向。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“循环前后搜索区间的数学含义必须一致，答案从不被错误排除”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[0,1] 上若 mid 向下取整却写 lo=mid，会在 lo=0、hi=1 时死循环”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“可统一采用 lower_bound 风格减少模板数量”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

二分写错都因循环条件、区间定义、收缩方式不配套。先定区间开闭(循环不变量:目标始终在区间内):闭区间 [lo,hi] → hi=n-1、while lo<=hi、收缩 mid±1;左闭右开 [lo,hi) → hi=n、while lo<hi、收缩 lo=mid+1/hi=mid。三者由区间统一决定,不能混。防死循环:每步区间必须缩小,「lo=mid 配 mid 上取整,hi=mid 配下取整」。记牢两套模板别现推。

简化版

详细版