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

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

这道题考二分查找的最坏情况步数。拿到1到100这个范围，先想每次猜中点能砍掉一半区间，再算2的几次方才够盖住100，向上取整就是答案。

很多同学看到100就下意识想log2(100)≈6.64，直接四舍五入选6，或者觉得2^6=64接近100就选B。其实二分最坏情况是区间长度减到1为止，必须满足2^k >= 100，k最小是7。还有人会选5，那是把2^5=32和100搞混了，或者误以为每次猜中点能直接命中目标，忽略了运气最坏时每次只能排除一半。

考点与概念

二分查找的核心是「每次猜中点，若不对则区间减半」。最坏情况就是运气最差，每次只排除一半，直到区间只剩1个数时才能猜中。因此最坏次数等于能覆盖该范围所需的最小2的幂次。

命题视角

题目特意选1-100，就是要卡住「知道二分思想但算不准步数」的考生。很多人背会了二分，一到具体数字就懵，要么用log2(100)≈6.64四舍五入，要么觉得2^6=64接近100就选6。命题人就是在测试你是否真正理解「二分是减半而非减固定值」以及「最坏情况必须满足2^k >= 范围」。