GESP 七级 · GESP 202506 C++ 七级 第 13 题

下面 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;
        }
    }
    return -1;
}

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

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

【考点】二分查找｜时间复杂度｜循环控制

🎯 考纲定位 本题考查《GESP 大纲》七级 C++ 算法模块中的二分查找与时间复杂度分析。七级要求掌握基础算法，二分查找是典型考察点。命题人用 $O(\log n)$ 的经典结论卡住大量只会记 $O(n)$ 线性搜索的学生，因为他们往往误判二分查找的循环次数。

🧠 解题思维 看到循环里每次都将搜索区间减半，立刻联想到二分查找。区间 $[low, high)$ 每轮缩小一半，迭代次数为 $\log_2 n$，每轮 $O(1)$ 操作，总平均时间复杂度 $O(\log n)$。若改成有序数组，二分不再适用；若改成无序数组，则需线性搜索。

🪤 陷阱拆解 选项 B 是线性搜索的经典复杂度，D 是常数时间，都是常见误区。命题人用 $O(\log n)$ 的结论卡住大量只会记 $O(n)$ 线性搜索的学生，因为他们往往误判二分查找的循环次数（以为是 $O(n)$ 或 $O(1)$）。循环条件 low < high 而非 low <= high 也是微妙之处，但平均复杂度仍为 $O(\log n)$。

🔄 反命题思维 若把循环条件改为 low <= high，迭代次数增加 1 仍为 $O(\log n)$；若改成非有序数组，则无法使用二分。刷到类似题先问：命题人想考我什么。