二分查找算法

二分查找算法

二分查找是高效的搜索算法。

基本原理

前提条件

有序数组
随机访问
​

核心思想

每次折半
逐步缩小范围
直到找到目标
​

标准实现

递归版本

def binary_search(arr, target, left, right):
    if left > right:
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)
    else:
        return binary_search(arr, target, left, mid - 1)
​

迭代版本

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
​

复杂度分析

时间复杂度

最好：O(1) - 直接找到
最坏：O(log n) - 一直折半
平均：O(log n)
​

空间复杂度

递归：O(log n) - 调用栈
迭代：O(1) - 常数空间
​

变种问题

查找第一个等于

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 继续向左找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result
​

查找最后一个等于

def find_last(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            result = mid
            left = mid + 1  # 继续向右找
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result
​

查找第一个大于等于

def find_first_ge(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left if left < len(arr) else -1
​

实际应用

在答案范围中二分

问题：最小的最大值
方法：在答案上二分
验证：检查是否可行
​

旋转数组

def search_rotated(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        
        # 判断哪边有序
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1
​

注意事项

1. 边界条件：left <= right还是left < right
2. 整数溢出：mid = left + (right - left) // 2
3. 死循环：确保区间每次都缩小
4. 返回值：明确找不到时返回什么

二分查找虽然简单，但细节容易出错。