单选题 适中
#19762

下面程序中,函数 query 的时间复杂度是( )。 # include <iostream> int query ( int n , int * a , in…

下面程序中,函数 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; 
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析
函数 query 使用 while 循环控制变量 l 和 r,初始分别为 0 和 n。每次循环计算 mid 为 (l + r) / 2,并根据 a[mid] 与 x 的大小关系更新 l 或 r。循环中 l 和 r 的范围持续缩小,直到 l >= r 结束。每次迭代将搜索区间大致减半,迭代次数与 n 的对数成正比。循环内部操作为常数时间。最终返回前的判断语句执行时间为常数。整个函数运行时间由循环次数和每次操作的时间复杂度共同决定。