S03-J02 · 二分查找：边界、旋转与答案二分

适用读者：写了十次二分，十次边界都不同的人。
前置：S03-B01。
实测环境：Python 3.12.3（复现三种错误写法）；实测日期 2026-11-05。
覆盖旧文：4、29、33、34、35、50、69、74、81（9 张卡，2,464 点）。
覆盖扩展：E-S03-015（统一模板：左闭右开 + 循环不变量）。
补写：#35 搜索插入位置（空壳卡，E-S03-113）；#4 的薄卡（A-2558）并入富卡。
上一篇：S03-J01 · 双指针与滑动窗口
下一篇：S03-J03 · 链表操作。

1. 一句话结论

二分只有一种正确的思考方式：先定义"区间里什么一定成立"（循环不变量），再决定 mid 归哪边。

写错的根本原因几乎都是"区间定义和边界更新不匹配"。三种典型错法，实测都能复现：

写法	问题	实测结果（数组 `[1,3,5,7,9,11]`）
`while (lo < hi)` + `hi = mid - 1`	会把答案排除	找 12 → 返回 5（应为 6）
`while (lo <= hi)` + `hi = mid`	可能死循环	找 2 → 死循环
混用 `mid = (lo+hi)/2` 与 `hi = mid - 1`	漏解/越界	小数组上"看起来对"，边界处崩

2. 唯一推荐模板：左闭右开 + `lower_bound`

// 返回第一个 >= target 的下标（不存在则返回 n）
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;          // 区间 [lo, hi)
    while (lo < hi) {                    // 区间非空
        int mid = lo + (hi - lo) / 2;    // 防溢出；向下取整
        if (a[mid] < target) lo = mid + 1;   // mid 及其左侧全部 < target
        else                 hi = mid;        // mid 可能是答案，保留
    }
    return lo;
}

为什么这样写不会错（三句话）：

要点	理由
`hi = n`（不是 `n-1`）	答案可能落在 `n`（全部元素都 `<target`）
`while (lo < hi)`	区间 `[lo,hi)`，空区间即结束，不会死循环
`hi = mid` 而非 `mid-1`	`mid` 自身可能是答案，不能排除

2.1 三个变体都由它派生

需求	写法
第一个 ≥ t	`lowerBound(t)`
第一个 > t	`lowerBound(t + 1)`（整数）或改为 `a[mid] <= t`
最后一个 ≤ t	`lowerBound(t + 1) - 1`
存在性判断	`pos < n && a[pos] == t`

"找到就返回"的写法只适合"存在性"场景，做边界题一律用 lower_bound——这是 90% 的人写错的根源。

3. 代表题精讲

3.1 #35 搜索插入位置（补写 `E-S03-113`）

题目：在有序数组中找 target 的下标；不存在则返回应插入的位置。

洞察：这就是 lower_bound 的定义——第一个 ≥ target 的位置。

int searchInsert(int[] a, int t) { return lowerBound(a, t); }

复杂度	值
时间	O(log n)
空间	O(1)

3.2 #34 找首末位置

int[] searchRange(int[] a, int t) {
    int l = lowerBound(a, t);
    if (l == a.length || a[l] != t) return new int[]{-1, -1};
    int r = lowerBound(a, t + 1) - 1;    // 第一个 > t 的位置减一
    return new int[]{l, r};
}

要点：两次二分都用同一个模板，第二个靠 t+1 复用——不需要写两套代码。

3.3 #33 / #81 旋转排序数组

#33（无重复）：mid 把数组分成"必有一半有序"，先判哪半有序，再看 target 是否在有序那半。

if (a[lo] <= a[mid]) {                    // 左半有序
    if (a[lo] <= t && t < a[mid]) hi = mid - 1; else lo = mid + 1;
} else {                                  // 右半有序
    if (a[mid] < t && t <= a[hi]) lo = mid + 1; else hi = mid - 1;
}

#81（有重复）：a[lo] == a[mid] == a[hi] 时无法判断哪半有序 → 只能 lo++, hi--，最坏退化 O(n)。

3.4 #4 两个正序数组中位数（薄卡并入富卡说明）

洞察：在较短数组上二分划分点 i，另一个数组的划分点 j 由总长度推出，保证"左半元素数 = 右半"。

// 条件：max(左半) <= min(右半)
// 用哨兵 ±∞ 处理越界，避免一堆 if

注意：j = (m + n + 1) / 2 - i，取 (m+n+1)/2 是为了让左半在奇数长度时多一个。

3.5 #69 / #50：二分答案与快速幂

#69 x 的平方根：二分答案——找最大 x 使 x*x <= n（用 long 防溢出）。

#50 Pow(x,n)：不是二分，是快速幂（二进制拆分指数）；负指数取倒数，n = -2³¹ 要单独处理。

3.6 #29 两数相除

洞察：不允许乘除，就用"减法翻倍"逼近——每次把除数翻倍直到不超过被除数，再从被除数里减掉。等价于在倍数空间上二分。

坑：-2³¹ / -1 溢出（结果 2³¹ 超 int），必须特判返回 Integer.MAX_VALUE。

3.7 #74 搜索二维矩阵

行列均有序（每行升序、每行首 > 上行末）→ 整块可视为一维有序数组，mid 映射：a[mid/n][mid%n]。

4. 9 题模式对照

题	模式	关键点
4	划分二分	短数组上二分，哨兵处理越界
29	减法翻倍	溢出一致性判断
33	旋转二分	先判有序半
34	两次 lower_bound	复用 `t+1`
35	lower_bound	补写（E-113）
50	快速幂	负指数、奇偶
69	二分答案	用 `long` 比较
74	一维映射	`mid/n`, `mid%n`
81	旋转 + 去重	无法判序时收缩

5. 五个误区

误区	真相
"二分只能用于有序数组"	更本质是"单调性"：答案空间单调即可二分（#69、#29）
"`mid` 取整方向无所谓"	影响死循环；`lo + (hi-lo)/2` 向下取整配 `hi=mid` 才安全
"找不到就直接返回 -1"	求边界时要返回插入位置（#35）
"有重复值不影响二分"	#81 会退化到 O(n)
"二分一定 O(log n)"	退化情形（#81）与"答案二分"的判定成本都要算进去

6. 自检

用"循环不变量"解释为什么 hi = mid 不能写成 mid-1。
while (lo <= hi) + hi = mid 为什么会死循环？举一个具体数组。
求"最后一个 ≤ t"怎么写（只能用 lowerBound）？
#81 为什么退化到 O(n)？
#69 的"二分答案"与原数组的单调性有什么关系？

7. 下一篇

S03-J03 · 链表操作：指针的四种基本动作

二分解决了"下标定位"，下一篇处理"没有下标"的结构：链表。会给虚拟头节点 + 三指针模板，并用实测说明迭代反转与递归反转的边界（递归在 3,000 个节点时就会 RecursionError）。

本篇属于系列《S03 · 数据结构与算法》。旧文来源：9 张题解卡；补写 #35（E-S03-113）。三种错误写法的实测结果为 2026-11-05。