单选题 适中
#16927

下面程序中,函数 query 的时间复杂度是( )。 def query ( n , a , x ) : left = 0 right = n while le…

下面程序中,函数 query 的时间复杂度是( )。

def query(n, a, x): 
    left = 0 
    right = n 
    while left < right: 
        mid = left + (right - left) // 2 
        if a[mid] >= x: 
            right = mid 
        else: 
            left = mid + 1 
    if left == n: 
        return -1 
    return left 
if __name__ == "__main__": 
    n = 10 
    x = 3 
    num = [1, 2, 2, 3, 3, 4, 5, 5, 6, 7] 
    print(query(n, num, x))
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析
函数 query 使用 while 循环控制 left 和 right 的范围,每次迭代将搜索区间缩小一半。循环条件依赖 left 和 right 的关系,且每次更新 mid 为 (left + right) // 2。当 mid 满足特定条件时,right 被赋值为 mid,否则 left 被更新为 mid + 1。循环持续直到 left 不小于 right。过程中仅进行常数时间的操作,无嵌套循环或递归。元素比较和指针移动均在固定时间内完成。整个执行路径由区间长度决定,每次将问题规模近似减半。