GESP 七级 · GESP 202403 C++ 七级 第 12 题

下面 search 函数的平均时间复杂度为（ ）。

int search(int n, int * p, int target) {
    int low = 0, high = n;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (target == p[middle]) {
            return middle;
        } else if (target > p[middle]) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return -1;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二进制搜索｜时间复杂度｜对数复杂度

🎯 考纲定位：GESP 七级算法模块。命题人卡住的是学生混淆线性搜索与二分搜索复杂度，或对数符号 $O(\log n)$ 的书写习惯。

🧠 解题思维：看到 while (low <= high) 和 middle = (low + high) / 2，立刻识别为二分搜索框架。每轮循环区间减半，初始区间 $n$，经过 $\log_2 n$ 次后区间长度接近 1。故时间复杂度为 $O(\log n)$。

🪤 陷阱拆解：A 选项 $O(n)$ 是线性搜索复杂度，命题人故意用"平均时间"诱导学生忽略二分性质；C 选项 $O(1)$ 混淆了单次比较与整体耗时；D 选项"可能无法返回"是语义陷阱，函数必返回索引或 -1。最阴险的是"平均"二字——若目标随机分布，二分搜索平均比较次数仍是 $O(\log n)$，但学生易误以为平均意味着线性。

🔄 反命题思维：若问"最坏时间复杂度"，答案同 $O(\log n)$；若问"平均比较次数"，需考虑目标不存在的情况，仍为 $O(\log n)$。刷到类似题先问：区间如何缩小？每次减半就是 $O(\log n)$，每次减一才是 $O(n)$。