9. 二分查找怎么写不容易错
二分查找是手撕代码中最经典也最容易写错的题。它的思想很简单：在有序数组中，每次取中间值，把搜索范围缩小一半。但真正写代码时，很多人会在 while 条件、left/right 更新、mid 计算、返回值上出错。测试岗面试中，二分查找非常适合考察边界意识。
准备二分查找，重点是先写稳基础版本，再扩展到查找第一个等于目标、最后一个等于目标、插入位置等变体。不要一开始就背很多模板，先把区间定义讲清楚。
一、二分查找前提
二分查找的前提是数据有序。
如果数组无序，不能直接用二分，除非先排序。但排序可能改变下标，所以要看题目要求。
适用场景：
- 有序数组查找目标值；
- 查找插入位置；
- 查找第一个或最后一个目标值；
- 在有序范围内查找边界；
- 某些答案具有单调性的题。
二、基础二分写法
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
这个版本使用闭区间 [left, right]，所以循环条件是 left <= right。
三、为什么 mid 这样写
mid = left + (right - left) // 2
这样可以避免某些语言中 left + right 溢出。Python 不会溢出，但养成这个习惯没坏处。
四、循环条件怎么选
如果使用闭区间 [left, right]：
while left <= right
如果使用左闭右开 [left, right)：
while left < right
面试中建议先固定一种模板，不要混用。初学者推荐闭区间版本。
五、查找插入位置
题目：如果目标不存在，返回应该插入的位置。
def search_insert(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
循环结束时，left 就是插入位置。
六、查找第一个目标值
数组中有重复元素时，查第一个等于 target 的位置。
def first_position(nums, target):
left, right = 0, len(nums) - 1
ans = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
if nums[mid] == target:
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
找到后不立即返回，而是继续向左找。
七、查找最后一个目标值
def last_position(nums, target):
left, right = 0, len(nums) - 1
ans = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
if nums[mid] == target:
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
找到后继续向右找。
八、二分常见错误
1. while 条件和区间定义不一致
闭区间却写 left < right，可能漏查最后一个元素。
2. left/right 更新不加 1 减 1
可能死循环。
3. 找到目标后立即返回
如果题目要求第一个或最后一个位置，不能立即返回。
4. 忘记空数组
空数组时 right = -1，循环不会进入，应返回 -1 或插入位置 0。
5. 无序数组直接二分
二分必须基于有序或单调性。
九、测试用例怎么补
二分查找要测：
- 空数组；
- 单元素命中；
- 单元素不命中；
- 目标在开头；
- 目标在结尾；
- 目标在中间；
- 目标不存在但应插入开头；
- 目标不存在但应插入末尾；
- 重复元素；
- 全部相同。
十、面试回答模板
如果面试官问“二分查找怎么写不容易错”，可以这样回答：
二分查找的前提是数组有序。我会先明确区间定义，比如使用闭区间
[left, right]，那么循环条件就是left <= right，目标小于中间值时right = mid - 1，大于时left = mid + 1。mid 用left + (right - left) // 2。基础查找命中直接返回，不存在返回 -1；如果是查插入位置，循环结束返回 left；如果查第一个或最后一个目标值，找到后不能马上返回，要继续向左或向右收缩。最后会用空数组、单元素、目标在首尾、不存在和重复元素验证。
十一、练习清单
- 基础二分查找；
- 查找插入位置；
- 查第一个目标值；
- 查最后一个目标值；
- 统计目标出现次数；
- 搜索旋转数组基础版；
- 平方根近似；
- 空数组测试；
- 重复元素测试；
- 总结闭区间模板。
二分查找写稳的关键是统一模板、明确区间、处理边界。不要混用不同写法。
配套刷题：
