二分查找算法详解

简介

二分查找是一种效率较高的查找算法，时间复杂度为 O(log n)。它的基本思想是：将已排序的数据集分成两半，将要查找的元素与分割点进行比较，再根据比较结果确定该元素在哪一半，并重复这个过程。

适用条件

  1. 数据必须是有序的（升序或降序）
  2. 数据集支持随机访问（例如数组）

基本实现

1. 基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int binary_search(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 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;  // 没找到返回-1
}

二分查找的变体

1. 查找第一个大于等于目标值的位置（下界）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 查找第一个大于等于target的位置（下界）
int lower_bound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

2. 查找最后一个小于等于目标值的位置（上界）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 查找第一个大于target的位置（上界）
int upper_bound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

完整版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;

// 普通二分查找
int binary_search(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 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;  // 没找到返回-1
}

// 查找第一个大于等于target的位置（下界）
int lower_bound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// 查找第一个大于target的位置（上界）
int upper_bound(vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
    
    // 普通二分查找
    int pos = binary_search(arr, 2);
    cout << "2的位置: " << pos << endl;  // 输出1（返回任意一个2的位置）
    
    // 下界
    int lower = lower_bound(arr, 2);
    cout << "第一个大于等于2的位置: " << lower << endl;  // 输出1
    
    // 上界
    int upper = upper_bound(arr, 2);
    cout << "第一个大于2的位置: " << upper << endl;  // 输出4
    
    return 0;
}

常见错误和注意事项

  1. 边界条件处理

    • 注意数组为空的情况
    • 注意只有一个元素的情况
    • 注意目标值不在数组范围内的情况

  2. 死循环问题

    • 确保每次循环都能缩小查找范围
    • mid 计算时防止整数溢出
    • 更新左右边界时要有 +1 或 -1 的操作

  3. 精度问题

    • 处理浮点数时需要考虑精度
    • 可以使用 eps（极小值）来判断相等

// 浮点数二分查找示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 浮点数二分查找
double binary_search_float(double left, double right, double target, int maxTry = 100) {
    double eps = 1e-8;  // 精度设置
    
    for(int i = 0; i < maxTry; i++) {
        double mid = left + (right - left) / 2;
        // 如果误差在精度范围内，返回结果
        if(fabs(mid - target) < eps) return mid;
        
        // 根据函数值调整区间
        if(mid < target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    return left;  // 返回近似解
}


性能分析

  1. 时间复杂度

    • 最好情况：O(1)，一次就找到
    • 平均情况：O(log n)
    • 最坏情况：O(log n)，需要查找到最后

  2. 空间复杂度

    • 迭代版本：O(1)
    • 递归版本：O(log n)，因为递归调用栈的开销

实战技巧

  1. 确定搜索范围

    • 明确左右边界的开闭区间
    • 考虑是否需要扩大搜索范围

  2. 选择合适的二分模板

    • 基础查找用标准模板
    • 查找左右边界时使用相应的变体
    • 处理重复元素时需要特别注意

  3. 防止整数溢出

    • 使用 mid = left + (right - left) / 2
    • 对于超大数据要考虑 long long 类型

练习题目推荐

  1. 基础练习：

    • LeetCode 704. 二分查找
    • LeetCode 35. 搜索插入位置
    • LeetCode 69. x的平方根

  2. 进阶练习：

    • LeetCode 33. 搜索旋转排序数组
    • LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
    • LeetCode 153. 寻找旋转排序数组中的最小值

  3. 实际应用：

    • LeetCode 287. 寻找重复数
    • LeetCode 300. 最长递增子序列
    • LeetCode 1095. 山脉数组中查找目标值

总结

二分查找是一个看似简单但实现细节很多的算法。掌握它需要：

  1. 理解基本原理和不同变体的使用场景
  2. 注意边界条件和各种特殊情况的处理
  3. 多练习不同类型的题目，培养对二分查找的敏感度
  4. 学会识别问题中的二分查找特征，灵活运用

记住：二分查找不仅限于在排序数组中查找元素，很多问题都可以转化为二分查找的思想来解决，特别是最大值最小化或最小值最大化的问题。

评论区仅供交流，有问题请 联系我 反馈。