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；如果查第一个或最后一个目标值，找到后不能马上返回，要继续向左或向右收缩。最后会用空数组、单元素、目标在首尾、不存在和重复元素验证。

十一、练习清单

基础二分查找；
查找插入位置；
查第一个目标值；
查最后一个目标值；
统计目标出现次数；
搜索旋转数组基础版；
平方根近似；
空数组测试；
重复元素测试；
总结闭区间模板。

二分查找写稳的关键是统一模板、明确区间、处理边界。不要混用不同写法。

配套刷题：

手撕代码