题目
LC 704 二分查找：给定一个
n 个元素
有序（升序）的整型数组
nums 和一个目标值
target，在数组中查找 target，若存在返回其下标，否则返回
-1。要求时间复杂度
O(log n)。
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
：给定一个非负整数
x，计算并返回
x 的
算术平方根，结果
只保留整数部分（即向下取整，
⌊√x⌋）。可用二分或牛顿法。
输入: x = 8
输出: 2 （√8 ≈ 2.828，小数部分舍去）
输入: x = 16
输出: 4
两道题是二分查找的"课内与课外"：704 是
标准形态 —— 在真实数组里找特定值；69 是
毕业形态 —— 数组根本不存在，"有序数组"是你自己构造的整数区间，要找的也不是某个值，而是一条
谓词边界。把 69 写对，说明二分真的学会了。
一、LC 704 核心洞察：二分是维持区间不变量的艺术
大多数人对二分的记忆是"取中间比较一下"——这是表象。二分的本质是一条
不变量：
若 target 在数组里，它的下标永远落在闭区间 [left, right] 内。
开局区间是整段
[0, n-1]。每一轮探中点
mid，三种结局：
nums[mid] == target：结案，返回 mid；nums[mid] < target：升序数组里 mid 左边（含 mid）全部比 target 小 —— 整段排除，left = mid + 1；nums[mid] > target：mid 右边（含 mid）全部比 target 大 —— 整段排除，right = mid - 1。
每轮排除一半，而不变量
一次都不被违反（被排除的那一半里绝不可能有答案）。当区间空了（
left > right），不变量的逆否命题直接给出结论：target 不在数组里，返回
-1。
所以整个算法只有三条铁律，且它们
都源自"闭区间 [left, right]"这一个约定 —— 换约定就得整套换（左闭右开的
[left, right) 版本是
while (left < right) +
right = mid，两派混用正是二分出错的根源）：
while (left <= right) —— 闭区间为空的条件恰好是 left === right + 1；mid = left + ((right - left) >> 1) —— 在 Java/C++ 里 (left + right) 会爆 int；left = mid + 1 / right = mid - 1 —— mid 已经检查过，不能带着它继续。
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right: # 闭区间非空
mid = left + ((right - left) >> 1) # 防爆 int
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1 # mid 检查过，跳过
else:
right = mid - 1
return -1
八行代码，三个细节全是考点。记住：
你不是在"折半查找"，你是在"每轮扔掉一半嫌疑、且绝不误伤嫌疑人"。
二、LC 69 核心洞察：答案不在数组里，在谓词的边界上
69 没有数组。但定义一个谓词：
P(k) := (k * k <= x)，k 在整数区间 [0, x] 上。
k 越大
k² 越大，所以
P 在整条区间上
必然"前真后假"：
k: 0 1 2 3 4 ... x
P(k): T T T F F ... F （x=8 时：T T T F F ... F）
"算术平方根的整数部分"是什么？就是
最后一个 true 的下标。于是 704 的模板一步不改地搬过来 —— 把
nums[mid] 换成
P(mid)：
def mySqrt(x):
lo, hi, ans = 0, x, 0
while lo <= hi:
mid = lo + ((hi - lo) >> 1)
if mid * mid <= x: # 谓词成立
ans = mid # 记下候选
lo = mid + 1 # 但不停手，继续向右找更大的真
else:
hi = mid - 1
return ans
和 704 的
唯一动作之差，正是"找特定值"与"找边界"的分岔口：
区间空时还有一条免费的性质：
ans === hi === lo - 1 ——
hi 恰好停在最后一个真上（单测把这条逐帧钉死）。这正是"红蓝边界"视角：二分结束时，
lo 是第一个假、
hi 是最后一个真，答案就在两指针的裂缝里。
这套"
答案二分"（对答案空间做二分）是 69 真正的考点：答案不必在某个现成数组里，只要你能构造一个
单调谓词，
[最小可能值, 最大可能值] 就是你的数组。LC 875（珂珂吃香蕉）、LC 1011（包裹运力）、LC 278（第一个错误版本）全是这一句话的换皮。
另一条路：牛顿法。求
k² = x 的切线迭代
k ← (k + x/k) / 2，整数版：
def mySqrt_newton(x):
if x < 2:
return x
k = x
while k * k > x:
k = (k + x // k) // 2 # 向 √x 二次收敛
return k
x = 8：
8 → 4 → 3 → 2，三步到位。牛顿法是
二次收敛 —— 每迭代一次有效位数翻倍，从
x ≈ 2³¹ 出发五六步就到底，理论更快；但面试写它的人不到一成，且"为什么整除版收敛到的是
⌊√x⌋ 而不是
⌈√x⌉"需要额外论证。二分版胜在每一步都走在第一节的模板上，
写不错。
三、动画怎么看
704 动画（
algo-viz--lc704）：顶部是有序数组格子行 —— 窗口
[left, right] 内正常、窗口外整段变灰（被排除的嫌疑区）、
mid 金框，
mid 指针在上方、
left/
right 指针在下方；中部是比较横幅（
nums[mid] ? target → 边界怎么动、排除几个）；底部面板实时显示区间大小与
累计排除数 —— 看着"已排除"一帧砍一半，
O(log n) 就不再是口号。默认 12 个元素找
31：4 探命中下标 9。
69 动画（
algo-viz--lc69）：顶部格子行是候选区间
0..x，每格上排
k、下排
k² ——
满足 k² ≤ x 的格子淡绿、不满足的灰，"前真后假"一眼可见，边界就站在绿灰交界处；
mid 金框、当前候选
ans 绿框、区间外虚线。中部横幅给出谓词判断与动作（"记 ans，继续向右" vs "hi 左移"）。默认
x = 8：4 探后
ans = 2。
两个动画共用同一套闭区间三件套，看完 704 再看 69，注意
只有"成立时"的动作不同。
四、完整推演表
704：
nums = [-1, 0, 3, 5, 9, 12, 15, 20, 26, 31, 38, 44]，
target = 31（与动画默认一致）。
12 → 6 → 3 → 1 → 命中：每探一次嫌疑减半，第 3 探是全程唯一一次"向右砍"。对比 miss 情形
target = 27：第 3 探变
right = 9，第 4 探
nums[9] = 31 > 27 变
right = 8，此时
left = 9 > right = 8 区间空，返回 -1 ——
交叉那一刻就是 -1 的证明。
69：
x = 8（谓词序列
T T T F F F F F F，边界在 2/3 之间）。
lo = 3 > hi = 2 区间空 → 返回
ans = 2。收工校验：
2² = 4 ≤ 8 且
3² = 9 > 8 —— 2 确实是最后一个真。注意第 2、3 探：谓词明明成立却
不收工，这就是边界二分与命中二分的指纹差异。
牛顿法（
x = 8）：
k = 8 → (8+1)/2 = 4 → (4+2)/2 = 3 → (3+2)/2 = 2，
2² = 4 ≤ 8 停，返回 2。
五、变体与同族题
- LC 35 搜索插入位置：704 删掉
return mid 那行，循环结束 return left —— miss 时 left 恰是第一个 ≥ target 的位置，即插入点。一行改动，边界二分雏形。
- LC 34 在排序数组中查找元素的第一个和最后一个位置：对"≥ target"和"≤ target"各跑一次边界二分。找边界才是二分的最大用武之地。
- LC 744 寻找比目标字母大的最小字母：同上，谓词
c > target。
- LC 278 第一个坏版本 / LC 374 猜数字大小：答案二分官方演示 —— 数组不存在，谓词（
isBadVersion / 大小比较）由系统提供。
- LC 875 珂珂吃香蕉 / LC 1011 在 D 天内送达包裹：答案二分进阶 —— 谓词要自己内层模拟算出来（速度 k 够不够快？运力 k 够不够用？），单调性一旦看破，剩下的就是 704 模板。
- LC 367 有效的完全平方数：与 69 同形，把
≤ 换成"是否存在恰好"。
- LC 162 寻找峰值 / LC 153 旋转数组最小数字：非全序二分 —— 没有 target 可比，但
nums[mid] 与邻居的关系足以判断"答案在哪半边"，不变量思想原样保留。
- LC 240 搜索二维矩阵 II：从右上角出发的阶梯二分，每步排除一行或一列。
一句话谱系：704 是识字课，35/34 是造句，278/875/1011 是作文，162/153 是阅读理解。
六、Java 版
class Solution {
// LC 704
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1); // 防 (left+right) 爆 int
if (nums[mid] == target) return mid;
if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}
class Solution {
// LC 69：long 版 —— 与推演表逐帧一致
public int mySqrt(int x) {
int lo = 0, hi = x, ans = 0;
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1);
if ((long) mid * mid <= x) { // 关键：mid*mid 先升 long 再比
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}
}
不想升
long 就把乘法改除法：
mid <= x / mid（整数除法下与
mid² <= x 等价）—— 但记得
mid == 0 时
x / mid 除零，需先
if (x < 2) return x; 再令
lo = 1。
七、边界情况
704：
- 空数组：
left = 0, right = -1，循环一次不进，返回 -1 —— 闭区间写法天然免疫；
- 单元素命中 / 未命中：
[-1] 找 -1 返回 0；找 0 则一探后 right = -1 交叉返回 -1；
- target 比所有元素都小 / 都大：全程单边收缩，
log₂n + 1 探封顶；
- 有重复元素：704 保证无重复；若有重复，本模板返回的是"碰巧命中的那个"，不保证最左最右 —— 那是 LC 34 的事。
69：
x = 0：mid = 0 成立记 ans = 0，返回 0；x = 1 同理返回 1；x = 2³¹-1：mid² 最大在 46340² = 2147395600 —— 恰好越过 int 上限 1 个单位，是溢出陷阱的"标准雷区"（2147395599 的答案是 46339，差一个数答案就变）；- 优化：
x ≥ 2 时 √x ≤ x/2 + 1，hi 可以从 x 收到 x/2 + 1，少一探。
八、复杂度
注意 69 的
log x 里
x 是
数值不是长度 —— 输入规模是
log x 个比特，所以严格说这是伪多项式；面试点到为止即可。
九、常见坑
while (left <= right) 写成 <：闭区间单元素时漏检 —— [-1] 找 -1 返回 -1。约定决定条件，混派必翻车。left = mid / right = mid 忘了 ±1：区间不再严格收缩，lo == hi 时原地打转死循环。记住不变量测试视角：每一帧区间宽度必须变小。(left + right) / 2 爆 int：Java/C++ 里 left + right 可超 2³¹-1 变负数。写 left + ((right - left) >> 1)。JS 无此坑（number 到 2⁵³），但 JS 的 >> 会先转 32 位整数 —— 数组长度超 2³⁰ 时得用 Math.floor。- 69 的
mid * mid 溢出：x = 2147395599 时 mid = 46340，mid² = 2147395600 > 2³¹-1，Java int 下变负数 → 谓词误判为真 → 答案错成 46340。升 long 或改除法（注意除零）。
- 答案二分忘了证单调：模板照搬的前提是谓词"前真后假"。
P(k) 不单调时二分的"排除一半"没有依据 —— 先证单调再动手。
(int) Math.sqrt(x) 一行流：对 x ≤ 2³¹-1 恰好安全（double 尾数 52 位），但面试官出题就是要你写二分/牛顿；且 x 一旦超过 2⁵³，double 连整数本身都存不准，浮点误差就是真坑。- 牛顿法整除的收敛方向：
(k + x//k) // 2 可能停在 ⌊√x⌋ + 1 再下来，循环条件必须是 k * k > x（用平方判停），不能数步数。
十、面试怎么答
704 的三段话：① 二分的本质是维持不变量"答案若在则恒在
[left, right]"，每轮排除一半且绝不误伤；② 三条铁律配套闭区间约定：
while (left <= right)、
mid = left + ((right - left) >> 1) 防爆 int、收缩必带 ±1 因为 mid 检查过；③ 区间空（
left > right）时返回 -1，其时
left 就是插入位置（LC 35 顺手带走）。
69 的三段话：① 构造谓词
P(k) = k² ≤ x，它在
[0, x] 上前真后假，
⌊√x⌋ 就是最后一个真 —— 这是
答案二分，数组是自己造的；② 与 704 唯一差异：P(mid) 成立时不返回，记候选
ans = mid 再向右，区间空时
ans（也即
hi）就是答案；③ 溢出对策：
mid² 升 long 或
mid <= x / mid（防
mid = 0 除零）。加分项：牛顿法
k ← (k + x/k)/2，二次收敛
O(log log x)。
若追问"为什么
left <= right 而不是
<"：不要背，现场推 —— 闭区间里
left == right 仍是
一个未检查的元素，用
< 就漏检；两派写法（闭区间 / 左闭右开）各自自洽，
混用才是事故现场。
结语
这一篇把二分从"技巧"还原成"纪律"：一条不变量、一个约定、三条铁律。704 教你
命中即收工，69 教你
成立不收工 —— 因为要找的从来不是某个元素，而是真与假的那道边界。边界一旦站稳，35、34、278、875、1011 全是同一句话的复读。
下一篇见。