GESP 五级 · GESP 202503 C++ 五级 第 11 题

若用二分法在 $[1, 100]$ 内猜数，最多需要猜（ ）次。

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】二分查找｜对数运算｜最坏情况分析

GESP 五级 算法模块，命题人卡住的是"线性思维惯性"——看到 100 就下意识想 100 或 10 次，但二分是指数级收敛，这是五级算法入门的分水岭。

二分法本质是每次猜中点，将搜索区间对半砍掉。[1,100] 第一次猜 50，若目标>50 则变[51,100]（剩 50 个数），第二次猜 75，若目标>75 则变[76,100]（剩 25 个数）……每猜一次剩余数量减半。最坏情况是目标始终落在被砍掉的半区边界，需要猜满 $\lceil \log_2 100 \rceil = 7$ 次才能把区间缩小到 1 个数。通法：对任意区间长度 $n$，二分查找最坏次数为 $\lceil \log_2 n \rceil$，即 $2^{k-1} < n \le 2^k$ 时 $k$ 次。

A 选项 100 是线性查找的直觉陷阱；B 选项 10 是常见误区，把对数底数当成 10（100 有两位），但二分法底数永远是 2；D 选项 5 是误以为 $2^5=32$ 能覆盖 100，忽略了二分是"对半砍"而非"直接覆盖"。题目最阴险的细节是"最多需要猜"——不是平均情况，而是最坏路径，如果你只记结论不推过程，就会掉进 B 或 D 的坑。

如果把区间改成[1,1024]，答案变成 11 次（$2^{10}=1024$）；改成[1,1000]仍是 10 次；改成[1,10000]就变成 14 次。这类题刷到先问自己：命题人想考我什么？是考对数底数、是考最坏情况、还是考区间长度与次数的关系？答案往往藏在这些变体的对比里。