二分查找:面试必会

二分查找是面试中出现频率最高的算法之一:代码不到十行,却藏着无数边界陷阱。本文从最朴素的版本讲起,带你写出一份"一次通过"的二分查找,并掌握它背后的思维模式——对"单调性"的利用。

1. 核心思想

在有序数组中查找目标值,每次取中间元素比较,把搜索区间砍掉一半。时间复杂度 O(log n):10 亿个元素也只需约 30 次比较。前提只有一个——数组必须有序。

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4))  # -1

2. 三个关键细节

• 循环条件:left <= right 才能保证区间为空时退出;若写成 <,会漏查最后一个元素。
• mid 的更新:写成 left + (right - left) // 2 可避免 left + right 整数溢出。
• 收缩方向:排除 mid 时必须 mid + 1 或 mid - 1,否则可能死循环。

3. 变体:查找左边界

当数组中有重复元素,题目往往要求"第一个等于 target 的位置"。此时找到目标后不立即返回,而是继续向左收缩:

def find_left(nums, target):
    left, right = 0, len(nums) - 1
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans if ans != -1 and nums[ans] == target else -1

print(find_left([1, 2, 2, 2, 3, 4], 2))  # 1
print(find_left([1, 2, 3, 4], 5))        # -1

对称地,把 nums[mid] >= target 改成 nums[mid] > target,就得到"第一个大于 target"的位置——这是求右边界和插入位置的通用套路。

4. 经典进阶:旋转数组

面试升级题:"升序数组在某点旋转(如 [4,5,6,1,2,3]),如何 O(log n) 找最小值?"思路:比较 mid 与右端点的值,判断哪一半是有序的,然后向"断裂处"收缩。

def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1   # 最小值在右半段
        else:
            right = mid      # 最小值在左半段(含 mid)
    return nums[left]

print(find_min([4, 5, 6, 1, 2, 3]))  # 1

注意这里循环条件变成了 left < right,且 right 收缩时不跳过 mid——两种模板的适用场景不同,一定要理解而不是死记。

5. 何时想到二分

• 数据有序,或经过一次变换后局部有序。
• 题目具有单调性:如"能否完成"随参数单调变化,即可对参数二分(答案二分法)。
• 要求 O(log n),而暴力是 O(n) 或 O(n²)。

💡 学习建议:把"标准版、左边界、右边界、旋转数组"四个模板各默写五遍,直到能闭眼写出;面试时先问清楚"有无重复元素、要找哪个边界",再动手。