单选题
适中
#19762
下面程序中,函数 query 的时间复杂度是( )。 # include <iostream> int query ( int n , int * a , in…
下面程序中,函数 query 的时间复杂度是( )。
答案与解析
正确答案:B
解析
函数 query 使用 while 循环控制变量 l 和 r,初始分别为 0 和 n。每次循环计算 mid 为 (l + r) / 2,并根据 a[mid] 与 x 的大小关系更新 l 或 r。循环中 l 和 r 的范围持续缩小,直到 l >= r 结束。每次迭代将搜索区间大致减半,迭代次数与 n 的对数成正比。循环内部操作为常数时间。最终返回前的判断语句执行时间为常数。整个函数运行时间由循环次数和每次操作的时间复杂度共同决定。