P4778 图书管理员（入门）

图书馆的书架上图书编号从 1 到 1000 连续排列。系统用二分法查找某一本指定的书，问需要比较多少次。

解题思路

1. 编号范围固定。 图书编号从 1 到 1000，也就是 low = 1，high = 1000。

2. 每次比较中间值。 mid = (low + high) / 2。如果 mid 等于要找的编号，就结束了；mid 大了就把 high 改成 mid - 1；mid 小了就把 low 改成 mid + 1。每比较一次，计数器 count 加 1。

3. 具体例子。 找编号 5：依次比较 500、250、125、62、31、15、7、3、5，一共 9 次，输出 9。

4. 边界情况。 找最小的编号 1：比较 500、250、125、62、31、15、7、3、1，也是 9 次；找最大的编号 1000：比较 500、750、875、938、969、985、993、997、999、1000，一共 10 次。端点的次数也要数对。

参考代码

// 图书管理员：编号从1到1000连续，统计用二分法找到指定图书需要的比较次数
#include <iostream>
using namespace std;
int main(){
    int bookNumber; // 要查找的图书编号
    cin >> bookNumber;
    int low = 1, high = 1000; // 图书编号范围
    int count = 0;            // 比较次数
    // 二分法查找图书
    while(low <= high){
        count++;
        int mid = (low + high) / 2; // 中间值
        if(mid == bookNumber){
            break; // 找到了
        } else if(mid > bookNumber){
            high = mid - 1; // 编号太大，往左半边找
        } else {
            low = mid + 1;  // 编号太小，往右半边找
        }
    }
    cout << count << endl;
    return 0;
}

复杂度分析

一共 1000 本书，二分法每次把范围减半，最多约 10 次比较（log2(1000) ≈ 10），时间复杂度是常数级别 O(1)。程序只用了几个变量，空间复杂度是 O(1)。