单选题
适中
#16927
下面程序中,函数 query 的时间复杂度是( )。 def query ( n , a , x ) : left = 0 right = n while le…
下面程序中,函数 query 的时间复杂度是( )。
答案与解析
正确答案:B
解析
函数 query 使用 while 循环控制 left 和 right 的范围,每次迭代将搜索区间缩小一半。循环条件依赖 left 和 right 的关系,且每次更新 mid 为 (left + right) // 2。当 mid 满足特定条件时,right 被赋值为 mid,否则 left 被更新为 mid + 1。循环持续直到 left 不小于 right。过程中仅进行常数时间的操作,无嵌套循环或递归。元素比较和指针移动均在固定时间内完成。整个执行路径由区间长度决定,每次将问题规模近似减半。