📘二分查找 Binary Search

2026-08-19
⭐⭐ GESP 5级

📖概念讲解

【考点 · 5级】二分查找，属于查找算法，核心思想：每次排除一半的搜索范围。


【说人话】想象你在字典里查一个词——你不会从第一页开始翻，而是直接翻到中间，判断目标在前半还是后半，然后继续折半。前提是数据必须有序（单调递增或递减）。

⚠️ 易错核心：mid = (l + r) / 2 在 l+r 很大时可能整数溢出！安全写法是 mid = l + (r - l) / 2。另外 l 和 r 的更新是 l = mid + 1 和 r = mid - 1（不是 mid），否则死循环！

💻代码示例

1#include <iostream>
2using namespace std;
3
4// 在有序数组 a[0..n-1] 中查找 target，返回下标或 -1
5int binarySearch(int a[], int n, int target) {
6 int l = 0, r = n - 1; // l:左边界 r:右边界（闭区间）
7 while (l <= r) { // 注意是 <=，不是 <！
8 int mid = l + (r - l) / 2; // 防溢出写法，等价于(l+r)/2
9 if (a[mid] == target) return mid; // 找到了，返回下标
10 else if (a[mid] < target) l = mid + 1; // 目标在右半边
11 else r = mid - 1; // 目标在左半边
12 }
13 return -1; // 没找到
14}
15
16int main() {
17 int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
18 int n = 10;
19 int idx = binarySearch(arr, n, 23);
20 if (idx != -1)
21 cout << "找到，下标=" << idx << endl;
22 else
23 cout << "未找到" << endl;
24 return 0;
25}
26// 输出: 找到，下标=5

🧩互动小测

Q1：对长度为 1000 的有序数组做二分查找，最多需要比较几次？

Q2：为什么 while 循环条件要用 l <= r 而不是 l < r？

🏋️动手练一练

📝 编程练习

给定一个升序排列的整数数组 nums 和一个目标值 target，用二分查找找到 target 在数组中的第一个出现位置（最左边）。如果不存在返回 -1。

提示：找到 target 后不要立即返回，继续往左半边缩小搜索范围，直到找不到为止。
输入：nums = [1, 2, 2, 2, 3, 4], target = 2
输出：1（第一个 2 的下标是 1）
参考答案： 
int lowerBound(int nums[], int n, int target) {
    int l = 0, r = n - 1, ans = -1;  // ans 记录最左边的下标
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) {    // 目标在左半边（含mid）
            ans = mid;               // 更新答案
            r = mid - 1;             // 继续往左找
        } else {
            l = mid + 1;             // 目标在右半边
        }
    }
    return ans;
}
// nums=[1,2,2,2,3,4], target=2 → 输出: 1

要点：当 nums[mid] == target 时，记录当前位置并往左收缩（r = mid - 1），这样才能找到第一个出现的位置。这就是 C++ 中 lower_bound 的底层逻辑。

📝易错点提醒

🔴 死循环：边界更新必须是 mid+1 / mid-1，不能写 l=mid / r=mid，否则 l==r 时不会前进。


🔴 整数溢出：(l+r)/2 当 l 和 r 都接近 INT_MAX 时会溢出，务必写成 l+(r-l)/2。


🔴 搞混两种二分：找"等于 target"用 l <= r 闭区间；找"第一个 ≥ target"（lower_bound）用 l < r 开区间模板也行，关键是理清自己要找什么。


🔴 忘记排序：二分查找的前提是数组有序！如果没排序，结果完全不可靠。

← 2026-08-18 2026-08-19 2026-08-20 →
学完这个知识点后点一下