二分思路人人会讲，写出来 bug 一堆。核心是区间定义要一以贯之。
两种写法，选一个别混
闭区间 [left, right]
def binary_search(nums, target):
left, right = 0, len(nums) - 1 # 右边界能取到
while left <= right: # 等号：区间非空
mid = left + (right - left) // 2 # 防溢出
if nums[mid] < target:
left = mid + 1 # mid 已排除
elif nums[mid] > target:
right = mid - 1
else:
return mid
return -1
半开区间 [left, right)
def lower_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 # 注意不是 mid-1
return left
三个最常错的点
mid = (left + right) // 2可能溢出：其他语言里是两个 int 相加溢出，用left + (right - left) // 2是通用好习惯；while里加不加等号取决于区间是否闭合，混用必死循环或漏答案；right = mid还是mid - 1同样取决于区间定义。
有重复元素怎么办
lower_bound 找第一个 >= target，upper_bound 找第一个 > target，两者配合就能数出 target 出现次数：
count = upper_bound(nums, target) - lower_bound(nums, target)
什么时候能用二分
不一定非要有序数组。只要能构造出一个单调的判定条件就能二分：
- 「吃掉这堆香蕉最少要几小时」（单调：速度越快时间越短）
- 「在 D 天内运完货物，船的最小载重」
- 「求平方根，保留整数部分」
这类叫二分答案，比在数组里找数更常考。
建议只背
lower_bound那套半开区间写法，左闭右闭容易在边界上纠结。
楼主 · 2026-09-28 13:21 · 浏览 6
