P4770 猜数游戏2（基础）

小童要玩猜数游戏：游戏给出的数在 1 到 10 亿（1000000000）之间，如果能在 20 次及以内猜中就能得到奖章。我们的任务就是判断小童能不能拿到奖章。

解题思路

1. 猜数范围是固定的。 不管给的数是多少，都是在 1 到 10 亿这个范围内猜，也就是 low = 1，high = 1000000000。

2. 每次猜中间值。 二分法就是每次取 mid = (low + high) / 2。如果 mid 正好等于要猜的数，就猜中了；如果 mid 比答案大，说明答案在左半边，把 high 改成 mid - 1；如果 mid 比答案小，说明答案在右半边，把 low 改成 mid + 1。

3. 数一数猜了多少次。 用一个计数器 count，每猜一次就加 1，直到 mid 等于答案为止，这样 count 就是真正需要的次数。比如要猜 500000000，第一次 mid 就是 (1 + 1000000000) / 2 = 500000000，正好等于答案，只要 1 次就能猜中，输出 YES。

4. 边界情况。 如果答案特别大，比如就是 1000000000，二分查找要一直往右半边找，大约 30 次才能找到，超过 20 次，输出 NO；如果答案是 1，也要一直往左半边找，大约 29 次，同样输出 NO。

5. 最后判断。 如果 count <= 20，输出 "YES"，否则输出 "NO"。

参考代码

// 猜数游戏2：在1到10亿范围内用二分法猜数，判断能否在20次以内猜中
#include <iostream>
using namespace std;
int main(){
    int number; // 要猜的数字
    cin >> number;
    int low = 1;               // 范围最小值
    int high = 1000000000;     // 范围最大值（10亿）
    int count = 0;             // 已经猜的次数
    // 二分法猜数，每次猜中间值
    while(low <= high){
        count++;
        int mid = (low + high) / 2; // 中间值
        if(mid == number){
            break;                  // 猜中了
        } else if(mid > number){
            high = mid - 1;         // 答案在左半边
        } else {
            low = mid + 1;          // 答案在右半边
        }
    }
    // 猜的次数不超过20次就能得到奖章
    if(count <= 20){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

复杂度分析

二分法每猜一次，范围就缩小一半。范围从 1 到 10 亿，最多经过约 30 次就能把范围缩到只剩一个数，所以时间复杂度是 O(log 10^9)，可以看成常数级别。程序只用了几个变量，空间复杂度是 O(1)。