考察二分查找的边界处理与正确性证明,而不是只写一个 mid 模板。
先定区间语义
[l, r] 或左闭右开 [l, r)。选定后全程保持一致,循环条件分别是 l <= r 和 l < r。mid 与边界
mid = l + (r - l) // 2 避免 l + r 溢出;在 Python 中整数不会溢出,但习惯仍建议这样写。nums[mid] < target 时 l = mid + 1,> 时 r = mid - 1;左闭右开:r = mid。l = mid 或 r = mid 配错循环条件;确保每次迭代区间严格缩小。lower_bound / upper_bound
>= target 的位置:if nums[mid] < target: l = mid + 1 else: r = mid(左闭右开),返回 l。<= target 可用对称写法,或转成 lower_bound(target+1)-1;有重复元素时明确要「第一个」还是「任意一个」。代码模板(左闭右开)
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
常见坑
r = len(nums) - 1 却用 l < r;mid 取整方向导致 l=mid 不前进;旋转数组/峰值题要先判断哪一侧有序;浮点二分要固定迭代次数而不是 l < r。题目与答案就在本页;收藏、批注和错题重练在应用内