二分查找 (Binary Search)

LeetCodeBinary Search二分查找算法

二分查找 (Binary Search)

二分查找是一种在有序数组中查找特定元素的搜索算法。每次查找将搜索空间减半，时间复杂度为O(log n)。

基础概念

标准二分查找

def binarySearch(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

二分查找模板

基本框架:
1. 初始化左右边界
2. 循环条件: left <= right
3. 计算中点: mid = left + (right - left) // 2
4. 根据条件调整边界
5. 返回结果

经典问题

1. 搜索旋转排序数组

LeetCode 33 - Search in Rotated Sorted Array

输入: nums = [4,5,6,7,0,1,2], target = 0

数组可视化:
原数组:   [0,1,2,4,5,6,7]
旋转后:   [4,5,6,7,0,1,2]
          左有序  右有序

查找过程:
1. mid = 7, 左半部分有序
2. target < 4, 搜索右半部分
3. mid = 0, 找到目标
def search(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

2. 寻找峰值

LeetCode 162 - Find Peak Element

输入: [1,2,3,1]

数组可视化:
    3
   /  \
  2    1
 /
1

查找过程:
1. mid = 2, nums[2] > nums[1]
2. 向右搜索较大值
3. 找到峰值3
def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
            
    return left

3. 寻找两个正序数组的中位数

LeetCode 4 - Median of Two Sorted Arrays

输入: nums1 = [1,3], nums2 = [2]

合并过程:
nums1: 1 3
nums2: 2
合并:  1 2 3

中位数: 2
def findMedianSortedArrays(nums1, nums2):
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    x, y = len(nums1), len(nums2)
    low, high = 0, x
    
    while low <= high:
        partitionX = (low + high) // 2
        partitionY = (x + y + 1) // 2 - partitionX
        
        maxLeftX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]
        minRightX = float('inf') if partitionX == x else nums1[partitionX]
        
        maxLeftY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]
        minRightY = float('inf') if partitionY == y else nums2[partitionY]
        
        if maxLeftX <= minRightY and maxLeftY <= minRightX:
            if (x + y) % 2 == 0:
                return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2
            else:
                return max(maxLeftX, maxLeftY)
        elif maxLeftX > minRightY:
            high = partitionX - 1
        else:
            low = partitionX + 1

4. 搜索二维矩阵

LeetCode 74 - Search a 2D Matrix

输入: matrix = [
  [1,  3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 60]
], target = 3

查找过程:
1. 将2D矩阵转换为1D数组
2. 应用标准二分查找
def searchMatrix(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
        element = matrix[mid // n][mid % n]
        
        if element == target:
            return True
        elif element < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return False

高级应用

1. 二分答案

问题类型:
- 最小值最大化
- 最大值最小化
- 平均值/中位数

解题步骤:
1. 确定答案范围
2. 二分猜测答案
3. 检查答案是否可行
4. 调整搜索范围

2. 实数域二分

求平方根示例:
left = 0, right = x
mid = (left + right) / 2

while right - left > 1e-6:
    if mid * mid > x:
        right = mid
    else:
        left = mid
    mid = (left + right) / 2

3. 二分图匹配

二分图示例:
A1 --- B2
|   \ 
|    \
A2 --- B1

匹配过程:
1. 选择未匹配点
2. 寻找增广路径
3. 更新匹配

常见技巧

  1. 边界条件处理
  2. 防止整数溢出
  3. 循环条件选择
  4. 区间开闭选择
  5. 重复元素处理

相关题目