x 的平方根

最朴素的做法，从 0 往上枚举，算 1 的平方、2 的平方、3 的平方，直到平方超过 x，停在前一个。能算对，但 x 很大时，比如二十亿，要试到四万多次，太慢。

为什么能二分：候选答案 m 越大，它的平方也越大，这是单调的。所以可以在区间 0 到 x 上对 m 二分。若 m×m 不超过 x，这个 m 可行、还能往更大试；若 m×m 超过 x，这个 m 太大、连同更大的都不行。一刀砍半，把逐个试从 O(√x) 降到 O(log x)。

准备 · 区间 [0,8]：把所有候选答案 0 到 8 排成一排，这排数全程不变。左指针 l 指 0、右指针 r 指 8，圈出搜索范围。答案 ans 先存 0。

第 1 轮 · 取中点 mid＝4：取中间位置，mid 等于 0 加 8 除以 2，得 4。下一步用它的平方和 x 比大小。

第 1 轮 · 判断 4×4 ＞ 8：4 乘 4 等于 16，大于 8。说明 4 以及比 4 更大的候选，平方都超了，都不可能是答案。这是负例：往小收。

第 1 轮 · 收右 r ＝ mid－1 ＝ 3：平方太大，把右指针 r 收到 mid 减 1，也就是 3。4 到 8 这半段，连同 mid 自己，灰掉丢弃。ans 仍是 0，没更新。

第 2 轮 · 取中点 mid＝1：范围缩到 0 到 3。新的中点，mid 等于 0 加 3 除以 2，向下取整得 1。算 1 的平方。

第 2 轮 · 判断 1×1 ≤ 8 → 记 ans：1 乘 1 等于 1，不超过 8。说明 1 是个可行答案，先把 ans 更新成 1。但右边可能还有更大的可行值，继续往右试。

第 2 轮 · 进左 l ＝ mid＋1 ＝ 2：mid 可行，记进 ans 等于 1，再把左指针 l 推到 mid 加 1，也就是 2，去右半 2 到 3 找有没有更大的可行答案。左边 0、1 不必再看。

第 3 轮 · 取中点 mid＝2：范围 2 到 3，中点 mid 等于 2 加 3 除以 2，向下取整得 2。算 2 的平方。

第 3 轮 · 判断 2×2 ≤ 8 → 更新 ans：2 乘 2 等于 4，仍不超过 8。又一个更大的可行答案，把 ans 更新成 2，再往右试。

第 3 轮 · 进左 l ＝ mid＋1 ＝ 3：ans 更新到 2，左指针 l 推到 3。现在 l 和 r 都指向 3，范围只剩一个候选。

第 4 轮 · 取中点 mid＝3：范围只剩 3 到 3，中点就是 3。算最后这个候选 3 的平方。

第 4 轮 · 判断 3×3 ＞ 8 → 收右：3 乘 3 等于 9，大于 8，太大。又一个负例：r 收到 mid 减 1，也就是 2，ans 不更新。这一收，l 是 3 越过了 r 是 2，范围空了。

结束 · 返回 ans＝2：收尾：l 越过 r，循环结束。ans 停在最后一次满足平方不超过 x 的值，正是 2，也就是 √8 的整数部分。

灵魂帧慢放 · 命中那一格：把核心动作慢放一遍：每轮只做一件事，拿 mid 的平方和 x 比。不超 x 就把这个 mid 记进 ans 再往大找，超了就往小找。2 是最后一个被记下的可行值，定格在它。

不一定要在数组里二分。只要答案越大越满足、或者越大越不满足，就能直接在答案的取值范围里二分。这一招叫二分答案。

雷区实演 · 返回 l 会差一：亲眼看差一坑：循环退出时，左指针 l 已经冲到 3，但 3 的平方超了 x，不是答案。真正的答案 2 是被 ans 锁住的。所以一定返回 ans，不能返回 l。

这题是二分答案的入门款：答案单调，就在答案范围上砍半。往上走，爱吃香蕉的珂珂、分割数组的最大值都是这一招。去二分专题用同一套骨架连着练，遇到卡点直接问小欧 AI 私教。