IT 面试题库

二分查找的循环不变量怎么定?为什么 mid 计算、边界收缩和死循环最容易出错?

中级编程题算法工程师后端开发工程师二分查找lower_bound循环不变量边界

题目

考察二分查找的边界处理与正确性证明,而不是只写一个 mid 模板。

参考答案

内容深度:详细 · 含示例/代码 · 来源:外部链接 · 未复核 · 29 天前更新

先定区间语义

mid 与边界

lower_bound / upper_bound

代码模板(左闭右开)

def lower_bound(nums, target):
    l, r = 0, len(nums)
    while l < r:
        mid = l + (r - l) // 2
        if nums[mid] < target:
            l = mid + 1
        else:
            r = mid
    return l

常见坑

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题