09 · 二分查找

来源： labuladong 二分查找统一模板 + 代码随想录循环不变量
核心价值： 在有序空间中用 O(log n) 找到目标，每次排除一半数据
题量： 6 题

---

一、本质理解

labuladong 对二分查找的定位：

二分查找 = 在有序空间中暴力穷举的优化版。
每次通过比较中间值，排除一半的搜索空间。

使用二分查找的关键条件

1. 有序性：搜索空间（或其某种性质）是单调的
2. 可随机访问：能用 O(1) 时间获取中间位置的元素
3. 可排除一半：能通过一次比较，确定目标在左半还是右半

---

二、核心模板

标准二分查找

def binary_search(nums, target):
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    
    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

寻找左侧边界（第一个 >= target 的位置）

def left_bound(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:  # nums[mid] >= target
            right = mid - 1  # 收缩右边界，锁定左侧
    
    if left >= len(nums) or nums[left] != target:
        return -1
    return left

寻找右侧边界（最后一个 <= target 的位置）

def right_bound(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1  # 收缩左边界，锁定右侧
        else:
            right = mid - 1
    
    if right < 0 or nums[right] != target:
        return -1
    return right

三种模板对比

模板	查找目标	while 条件	mid 比较	返回值
标准	精确值	left <= right	== 直接返回	索引或 -1
左边界	第一个 >= target	left <= right	>= 时收缩 right	left
右边界	最后一个 <= target	left <= right	<= 时收缩 left	right

---

三、变体应用

搜索旋转排序数组

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        
        if nums[left] <= nums[mid]:  # 左半有序
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # 右半有序
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

寻找旋转排序数组最小值

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

搜索二维矩阵（将矩阵视为一维数组）

def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    left, right = 0, m * n - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        val = matrix[mid // n][mid % n]  # 关键：将一维索引转二维
        if val == target:
            return True
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

寻找两个正序数组的中位数（Hard）

def find_median_sorted_arrays(nums1, nums2):
    # 在较短的数组上二分
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    m, n = len(nums1), len(nums2)
    left, right = 0, m
    
    while left <= right:
        i = (left + right) // 2  # nums1 的分割线
        j = (m + n + 1) // 2 - i  # nums2 的分割线
        
        nums1_left = nums1[i - 1] if i > 0 else float('-inf')
        nums1_right = nums1[i] if i < m else float('inf')
        nums2_left = nums2[j - 1] if j > 0 else float('-inf')
        nums2_right = nums2[j] if j < n else float('inf')
        
        if nums1_left <= nums2_right and nums2_left <= nums1_right:
            if (m + n) % 2 == 0:
                return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
            else:
                return max(nums1_left, nums2_left)
        elif nums1_left > nums2_right:
            right = i - 1
        else:
            left = i + 1

---

四、Hot 100 二分查找题目清单

题号	题目	难度	核心技巧	建议用时
35	搜索插入位置	Easy	左边界二分	20 min
74	搜索二维矩阵	Medium	二维转一维二分	25 min
34	查找元素首末位置	Medium	左右边界两次二分	30 min
33	搜索旋转排序数组	Medium	判断有序区间	35 min
153	寻找旋转最小值	Medium	比较 mid 和 right	30 min
4	两个正序数组中位数	Hard	在短数组上二分分割线	45 min

---

五、易错点与技巧

1. 循环条件：left <= right（闭区间）vs left < right（开区间），保持一致即可
2. mid 计算：mid = left + (right - left) // 2 防溢出
3. 边界收缩：关键是确定收缩后新区间是否包含 mid
4. 旋转数组：先判断 mid 在哪段有序区间，再判断 target 的位置
5. 答案二分：有时候不是对数组二分，而是对答案的值域二分（如求最大值最小化问题）

---

六、复杂度总结

场景	时间复杂度	空间复杂度
标准二分	O(log n)	O(1)
旋转数组	O(log n)	O(1)
二维矩阵二分	O(log(mn))	O(1)
中位数问题	O(log min(m,n))	O(1)

---

七、参考与延伸

• 03-数组与矩阵（搜索二维矩阵的两种方法）
• Python bisect 模块：bisect_left 和 bisect_right 是二分查找的内置实现
• labuladong 二分查找详解：https://labuladong.online/algo/
• 代码随想录二分专题：https://programmercarl.com/