P4773 字典找字（入门）

一本字典的 15 到 45 页之间有一页是我们想找的，用二分法快速翻到那一页，问需要翻多少次（中间值 mid = (最大值 + 最小值) / 2）。

解题思路

1. 确定翻页范围。 页码范围从 15 到 45，也就是 low = 15，high = 45。

2. 每次翻到中间。 mid = (low + high) / 2。如果 mid 就是要找的页码，就停止；如果 mid 比目标大，说明目标在左边，把 high 改成 mid - 1；如果 mid 比目标小，就往右边翻，把 low 改成 mid + 1。每翻一次计数加 1。

3. 具体例子。 要找 18：第一次 mid = (15+45)/2 = 30，比 18 大，范围变成 [15, 29]；第二次 mid = (15+29)/2 = 22，还比 18 大，范围变成 [15, 21]；第三次 mid = (15+21)/2 = 18，正好找到。一共 3 次，输出 3。

4. 边界情况。 如果要找的是端点 15，会依次比较 30、22、18、16、15，共 5 次；要找 45 也同样 5 次。这些都要能正确数出来。

参考代码

// 字典找字：在15到45页之间用二分法找到指定页码，统计查找次数
#include <iostream>
using namespace std;
int main(){
    int page; // 要查找的页码
    cin >> page;
    int low = 15, high = 45; // 页码范围
    int count = 0;           // 查找次数
    // 二分法翻字典
    while(low <= high){
        count++;
        int mid = (low + high) / 2; // 中间值
        if(mid == page){
            break; // 翻到要找的页码了
        } else if(mid > page){
            high = mid - 1; // 页码太大，往前翻
        } else {
            low = mid + 1;  // 页码太小，往后翻
        }
    }
    cout << count << endl;
    return 0;
}

复杂度分析

页码一共 31 个（15 到 45），二分法每次减半，最多约 5 次就能找到，时间复杂度是 O(log 31)，也就是常数级别。程序只用了几个变量，空间复杂度是 O(1)。