二分查找算法详解：从原理到实现

二分查找（Binary Search）是一种在有序数组中查找特定元素的算法，时间复杂度为 O(log n)，是效率极高的搜索算法。

算法原理

二分查找的核心思想是分而治之：

1. 将数组分为两半
2. 比较中间元素与目标值
3. 根据比较结果决定在左半部分或右半部分继续查找
4. 重复上述过程直到找到目标或确定不存在

基本实现

Python 实现

def binary_search(arr, target):
    """
    二分查找算法
    
    Args:
        arr: 有序数组
        target: 目标值
    
    Returns:
        目标值的索引，如果不存在返回 -1
    """
    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

# 示例
arr = [1, 3, 5, 7, 9, 11, 13, 15]
result = binary_search(arr, 7)
print(f"找到目标值，索引为: {result}")  # 输出: 3

JavaScript 实现

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

时间复杂度分析

• 时间复杂度：O(log n)
• 空间复杂度：O(1)（迭代实现）或 O(log n)（递归实现）

为什么是 O(log n)？

每次迭代都将搜索范围减半：

• 第 1 次：n 个元素
• 第 2 次：n/2 个元素
• 第 3 次：n/4 个元素
• ...
• 第 k 次：n/2^k 个元素

当 n/2^k = 1 时，k = log₂n，所以时间复杂度为 O(log n)。

变种问题

1. 查找第一个等于目标值的位置

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

2. 查找最后一个等于目标值的位置

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

应用场景

1. 有序数组查找：最直接的应用
2. 查找边界问题：如查找插入位置
3. 数值计算：在连续函数中查找满足条件的值
4. 数据库索引：B+ 树等索引结构的基础

注意事项

1. 数组必须有序：这是二分查找的前提条件
2. 整数溢出：计算 mid 时注意 (left + right) // 2 可能溢出，建议使用 left + (right - left) // 2
3. 边界条件：注意处理空数组、单元素数组等特殊情况

总结

二分查找是算法学习中的经典问题，掌握它对于理解分治思想和优化搜索效率非常重要。在实际应用中，要确保数据有序，并注意处理各种边界情况。