核心要点

  • 前提是有序；用 mid = left + (right-left)//2 防溢出，明确区间是左闭右开还是左闭右闭

  • lower_bound 求第一个 ≥ target 的位置，upper_bound 求第一个 > target 的位置

  • 易错点：循环条件与区间收缩要自洽，否则死循环或漏判；用循环不变量验证正确性

标准回答

二分查找在有序数组上每次排除一半区间，时间从 O(n) 降到 O(log n)。写对二分的关键是始终维护清晰的循环不变量，并让循环条件与区间收缩方式自洽。这里统一用左闭右开 [left, right) 区间。基础二分判等即可；而求边界的变体——lower_bound 返回第一个不小于 target 的下标、upper_bound 返回第一个大于 target 的下标——只是判断条件不同。两者结合可求一个值在数组中的出现次数。下面给出实现：

python
def lower_bound(nums, target):
    # 第一个 >= target 的下标，区间 [left, right)
    left, right = 0, len(nums)
    while left < right:                 # 区间非空时继续
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1             # mid 不满足，舍弃左半含 mid
        else:
            right = mid                # mid 可能是答案，保留在右边界
    return left                         # 不变量：left 左侧全 < target


def upper_bound(nums, target):
    # 第一个 > target 的下标
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    return left


def count_target(nums, target):
    # 目标出现次数 = upper_bound - lower_bound
    return upper_bound(nums, target) - lower_bound(nums, target)


if __name__ == '__main__':
    a = [1, 2, 2, 2, 3, 5]
    print(lower_bound(a, 2))   # 1
    print(upper_bound(a, 2))   # 4
    print(count_target(a, 2))  # 3
    print(lower_bound(a, 4))   # 4 (插入位置)

常见误区

⚠️ 常见踩坑

mid 用 (left+right)//2 在超大下标可能溢出（其他语言），统一写 left+(right-left)//2；左闭右开时 right 初值是 len(nums) 不是 len-1，循环条件是 left < right。

追问

追问 1：为什么二分能保证不死循环？

每轮区间长度严格缩小：left=mid+1 至少使 left 增 1，right=mid 因 mid<right 必使 right 减小。区间单调收缩到空（left==right）后退出，故 O(log n) 步内必然终止。

追问 2：在旋转有序数组中查找如何用二分？

每次先判断哪一半是有序的：比较 nums[mid] 与 nums[left]。若左半有序且 target 落在 [nums[left], nums[mid]) 内则收缩到左半，否则去右半；右半有序时对称处理。仍是 O(log n)。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

🎯 相关面试题