二分查找

概念讲解

什么是二分查找？

二分查找是在有序数组中查找目标值的算法，每次将搜索范围缩小一半。

时间复杂度

$O(\log n)$

整数二分

模板一：找左边界

123456789101112int binarySearch(int a[], int n, int target) {
    int left = 0, right = n - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

模板二：找右边界

123456789101112int binarySearch(int a[], int n, int target) {
    int left = 0, right = n - 1;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (a[mid] <= target) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

STL 函数

lower_bound

找第一个 ≥ target 的位置。

123456// 函数原型（需 #include <algorithm>）
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

// 示例
int* it = lower_bound(a, a + n, target);
int pos = it - a;

upper_bound

找第一个 > target 的位置。

123456// 函数原型（需 #include <algorithm>）
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

// 示例
int* it = upper_bound(a, a + n, target);
int pos = it - a;

二分答案

当答案具有单调性时，可以二分答案。

12345678910111213bool check(int mid) {
    // 检查 mid 是否可行
}

int left = minVal, right = maxVal;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (check(mid)) {
        right = mid;
    } else {
        left = mid + 1;
    }
}

考点分析

初赛考查方式

1. 选择题： 二分查找过程
2. 程序阅读： 二分程序
3. 编程题： 二分应用

常见考点

• 二分查找过程
• lower_bound/upper_bound
• 二分答案

例题精讲

例题 1：二分查找

题目： 在 [1, 3, 5, 7, 9] 中查找 5。

解答：

left=0, right=4, mid=2, a[2]=5, 找到！

例题 2：二分答案

题目： 求 sqrt(10) 的整数部分。

解答：

left=0, right=10, mid=5, 5*5=25>10, right=4
left=0, right=4, mid=2, 2*2=4<10, left=2
left=2, right=4, mid=3, 3*3=9<10, left=3
left=3, right=3, 结束

答案是 3。

练习题

1. 二分查找的时间复杂度是多少？

2. lower_bound 和 upper_bound 的区别是什么？

3. 什么情况下可以二分答案？

易错点

⚠️ 注意：

1. 二分查找要求数组有序
2. 注意边界条件（< 还是 <=）
3. mid 计算防止溢出
4. 二分答案需要单调性