GESP 七级 · GESP 202512 C++ 七级 第 8 题

下面程序中，函数 query 的时间复杂度是（ ）。

#include <iostream>

int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }

    if (l == n) return -1;
    return l;
}

int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};

    std::cout << query(n, num, x) << "\n";
    return 0;
}

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

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

【考点】二分查找｜对数复杂度｜有序数组前提

1. 🎯 考纲定位

本题考查二分查找在 GESP 七级「算法与数据结构」模块中的基础应用。命题人卡住的是考生对循环迭代次数与对数关系的直观感知——绝大多数人看到 while 循环就默认 O(n)，除非真正理解每次区间减半的数学本质。