P4772 图书管理员（入门）

图书馆有个三层书架：第一层图书编号从 1 到 36，第二层从 1 到 15，第三层从 5 到 26，编号都是连续的。现在要从每层拿下一本书，统计用二分法找到这本书需要的比较次数。

解题思路

1. 把每一层都看成一段连续的编号范围。 第一层范围 [1, 36]，第二层范围 [1, 15]，第三层范围 [5, 26]。每层单独统计，互不影响。

2. 写一个函数统计次数。 函数 countTimes(要找的编号, 左端点, 右端点) 在范围内二分：取 mid = (左端点 + 右端点) / 2，每比较一次计数加 1。如果 mid 等于要找的编号就结束；mid 大了就改右端点，mid 小了就改左端点，最后返回总次数。

3. 具体例子。 比如三层都要找 5：第一层 [1,36] 依次比较 18、9、4、6、5，共 5 次；第二层 [1,15] 比较 8、4、6、5，共 4 次；第三层 [5,26] 比较 15、9、6、5，共 4 次。所以输出 "5 4 4"。

4. 边界情况。 如果找的是范围的端点，比如第一层找 1，会比较 18、9、4、2、1 共 5 次；找 36 会比较 18、27、32、34、35、36 共 6 次。每个端点都要能正确统计。

参考代码

// 图书管理员：分别统计三层书架用二分法找到指定图书需要的比较次数
#include <iostream>
using namespace std;
// 统计在[low,high]范围内用二分法找到target需要的比较次数
int countTimes(int target, int low, int high){
    int count = 0;
    while(low <= high){
        count++;
        int mid = (low + high) / 2; // 中间值
        if(mid == target){
            break; // 找到了
        } else if(mid > target){
            high = mid - 1; // 编号太大，往左半边找
        } else {
            low = mid + 1;  // 编号太小，往右半边找
        }
    }
    return count;
}
int main(){
    int book1, book2, book3;
    cin >> book1 >> book2 >> book3;
    // 第一层编号1~36，第二层编号1~15，第三层编号5~26
    int times1 = countTimes(book1, 1, 36);
    int times2 = countTimes(book2, 1, 15);
    int times3 = countTimes(book3, 5, 26);
    cout << times1 << " " << times2 << " " << times3 << endl;
    return 0;
}

复杂度分析

每一层都只有几十本书，二分法每次减半，每层最多比较 log2(36) ≈ 6 次，三层加起来也不过十几次，时间复杂度可以看成 O(1)。程序只用了几个变量，空间复杂度是 O(1)。