GESP 六级 · GESP 六级样题（C++ 组） 第 2 题

小明想了一个 1 到 100 之间的整数。你可以做多次猜测，每次猜测之后，如果你没有猜中，小明会告诉你，你猜的数比他想的数大还是小。你希望你在运气最坏的情况下花费最少的次数猜中，请问你运气最坏的情况下会猜（ ）次？（包括最后猜中的那次）。

这题本质就是算二分查找的最坏步数。每次猜中点，区间减半，直到只剩1个数。直接算2的几次方能覆盖100，向上取整就是答案。

最容易掉进两个坑：一是死磕线性搜索，觉得100个数就要猜100次；二是算错指数，比如以为2的6次方就够了，或者把向上取整搞成向下取整。记住，题目问的是运气最坏的情况，必须按二分的最坏路径算，不能只看平均或者最优。

1. 考点与概念

这道题考查的是二分查找在信息论层面的下界。核心概念很简单：每次猜测，你只能得到“更大”或“更小”两个反馈。这意味着无论你怎么猜，猜一次最多能把剩下的可能性砍掉一半。要想在1到100之间必中，你必须把区间不断对半劈，直到只剩一个数。这个“劈”的过程，就是数学上的对数增长。

2. 命题视角：为什么是B？

命题人放这道题，就是想卡住那些只会线性枚举、不懂“用每次猜测获取最大信息量”的考生。线性搜索覆盖100个数需要100次，但二分搜索7次就能覆盖127个数。题目问“运气最坏的情况下花费最少的次数”，其实就是求⌈log₂100⌉。这个值恰好是7，所以答案选B。