binary_search.md

二分搜索 (Binary Search) 教案

1. 算法基础理论资料

算法定义与背景

二分搜索（Binary Search），也称折半搜索，是一种在有序数组中查找特定元素的高效搜索算法。由John Mauchly在1946年首次提出。该算法充分利用了数组的有序性，通过不断将搜索范围减半来快速定位目标元素。

问题定义

在一个已排序的数组中查找指定元素的位置，若存在则返回其索引，否则返回不存在的标识。

数学基础

基于分治法的思想和对数函数的数学概念。

2. 算法详细描述

算法思想

在有序数组中，通过比较中间元素与目标值的大小关系，每次将搜索范围缩小一半，直到找到目标元素或搜索范围为空。

算法步骤

1. 设定数组的左边界left和右边界right；
2. 当left <= right时，计算中间位置mid = (left + right) / 2；
3. 比较arr[mid]与目标值target：
   • 如果arr[mid] == target，则找到目标，返回mid；
   • 如果arr[mid] < target，则目标在右半部分，更新left = mid + 1；
   • 如果arr[mid] > target，则目标在左半部分，更新right = mid - 1；
4. 重复步骤2-3，直到找到目标或left > right；
5. 若未找到目标，返回不存在的标识（如-1）。

伪代码

算法 BinarySearch(arr, target)
输入：已排序数组arr，长度为n；目标值target
输出：目标值在数组中的索引，若不存在则返回-1

left = 0
right = n - 1
while left <= right do
    mid = (left + right) / 2
    if arr[mid] == target then
        return mid
    else if arr[mid] < target then
        left = mid + 1
    else
        right = mid - 1
return -1

3. 算法实现

Python实现

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

# 递归实现
def binary_search_recursive(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_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

Java实现

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// 递归实现
public static int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

4. 复杂度分析

时间复杂度

• 最好情况：O(1) - 第一次就找到目标元素
• 最坏情况：O(log n) - 需要查找到最后
• 平均情况：O(log n)

空间复杂度

• 迭代版本：O(1) - 只需要常数级别的额外空间
• 递归版本：O(log n) - 递归调用栈的深度

数学证明

每次比较后搜索范围减半，所以最多需要log₂(n)次比较就能确定元素是否存在。

5. 示例与案例

简单示例

数组：[1, 3, 5, 7, 9, 11, 13, 15] 查找：7 过程：中间元素是9 > 7，在左半部分查找；中间元素是5 < 7，在右半部分查找；找到7，返回索引3。

复杂案例

1. 查找边界元素（第一个或最后一个元素）
2. 查找不存在的元素
3. 在大型数据集中查找

边界条件

• 空数组
• 只有一个元素的数组
• 查找第一个元素
• 查找最后一个元素
• 查找不存在的元素

6. 算法可视化

可以通过动画演示搜索范围如何逐步减半，以及中间元素如何引导搜索方向。

7. 优缺点分析

优势

• 时间复杂度低，效率高
• 实现相对简单
• 适用于静态数据的大规模查找

局限性

• 要求数据必须是有序的
• 对于频繁变动的数据，维护有序性成本高
• 只适用于支持随机访问的数据结构（如数组）

与其他算法的比较

相比于线性搜索的O(n)时间复杂度，二分搜索的O(log n)具有显著优势，但要求数据有序。

8. 应用场景

实际应用

• 在有序数组中查找元素
• 在数据库索引中定位记录
• 在字典中查找单词
• 版本控制中查找第一次出现bug的提交
• 数学计算中求解方程的根

相关领域

• 数据库系统
• 搜索引擎
• 数值计算
• 竞争性编程

9. 练习与作业

理论题

1. 证明二分搜索的时间复杂度为O(log n)。
2. 比较迭代和递归实现的空间复杂度差异。

编程题

1. 实现二分搜索算法，处理各种边界条件。
2. 实现查找第一个大于等于目标值的元素位置的变体。
3. 实现查找最后一个小于等于目标值的元素位置的变体。

项目作业

设计一个搜索引擎的核心模块，使用二分搜索在已排序的网页索引中快速定位相关内容。

10. 扩展阅读

研究论文

• 二分搜索的各种变体和优化研究
• 在分布式系统中的应用

进阶资料

• 《算法导论》中的搜索算法章节
• 《编程珠玑》中关于二分搜索的应用实例
• 插值搜索、指数搜索等相关算法

相关算法

• 线性搜索
• 插值搜索
• 指数搜索
• 三分搜索