CC++ & Algorithm

二分查找——猜数字游戏的制胜法宝

困难13
语言版本：C++
概述：二分查找就像在有序列表中猜数字，每次从中间猜，一半一半地缩小范围，超快找到目标。

二分查找：猜数字游戏的制胜法宝（CSP-J 精讲）

这是什么？用来干什么？

二分查找（Binary Search）是一种在 有序数组 中快速找到某个特定值的位置的算法。它的名字很形象：每次把搜索范围“分成两半”，然后只保留可能含有目标的那一半，继续重复这个过程，直到找到目标或者范围变为空。

你玩过“猜数字”游戏吗？对手心里想一个 1～100 之间的整数，你每次猜一个数，对方会告诉你“大了”或“小了”。最聪明的猜法就是每次猜 中间的数，比如第一次猜 50，如果大了，说明目标在 1～49 之间；然后猜 25……这样每猜一次就能排除一半的数，最多猜 7 次就能中（因为 2⁷ = 128 > 100）。二分查找用的正是这个原理。

在编程竞赛（比如 CSP-J）中，二分查找常用于：

  • 在有序数组中快速判断某个数是否存在；
  • 查找某个值第一次出现或最后一次出现的位置；
  • 在单调函数上求满足条件的最小/最大值（“二分答案”）等。

它的时间复杂度为 O(log n)，非常高效，即使有 10 亿个元素，也只需要大约 30 次比较。

核心思想：每次砍掉一半

二分查找的前提是 数组必须有序（从小到大或从大到小）。每次操作分为三步：

  1. 取中间元素：计算当前搜索区间的中间下标 mid。
  2. 比较：把 arr[mid] 和目标值 target 比较。
    • 如果相等，直接返回 mid（找到啦！）。
    • 如果 arr[mid] < target，说明目标在右半部分（因为数组从小到大排），所以把左边界移到 mid + 1。
    • 如果 arr[mid] > target，说明目标在左半部分，把右边界移到 mid - 1。
  3. 重复：直到左边界超过右边界（说明没找到）。

生活例子：你在新华字典里查“水”这个字。字典的页码按拼音顺序排列（有序），你会先翻到中间某一页，看看那个拼音是“L”还是“S”？如果翻到的是“M”，而“水”的首字母是“S”，那么你就知道肯定在后半本，于是扔掉前半本，继续在后半本中间翻……这就是二分查找。

手把手写二分查找代码

下面是一个标准的二分查找实现，在有序数组中查找目标值，返回下标（没找到返回 -1）。每一行都加了中文注释，方便理解。

#include <iostream>
#include <vector>
using namespace std;

// 二分查找函数，arr是有序数组，target是要找的值
int binarySearch(vector<int>& arr, int target) {
    // 定义左右边界，左闭右闭区间 [left, right]
    int left = 0;                     // 左边界下标
    int right = arr.size() - 1;       // 右边界下标

    // 当左边界 <= 右边界时，说明区间还有元素
    while (left <= right) {
        // 计算中间下标，用 left + (right - left) / 2 防止溢出
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {     // 找到了！
            return mid;
        } else if (arr[mid] < target) {
            // 目标在右半部分，移动左边界到 mid+1
            left = mid + 1;
        } else {
            // 目标在左半部分，移动右边界到 mid-1
            right = mid - 1;
        }
    }

    return -1; // 循环结束没找到，返回 -1
}

int main() {
    // 一个从小到大排好序的数组（比如考试成绩排名）
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 7;   // 想找的分数

    int index = binarySearch(arr, target);
    if (index != -1) {
        cout << "找到了，下标是 " << index << endl;
    } else {
        cout << "没找到" << endl;
    }

    return 0;
}

运行结果：

找到了，下标是 3

边界条件详解：左闭右闭 vs 左闭右开

二分查找最坑的地方就是 边界条件。上面的代码用的是 左闭右闭 区间，即 [left, right]。另一种常见写法是 左闭右开 区间 [left, right)，循环条件变成 while (left < right)，更新边界时 right = mid（因为右边界不包含）。初学者容易混淆，导致死循环或漏掉元素。

记忆口诀（左闭右闭）：

  • 初始：left = 0, right = n-1
  • 循环条件：left <= right
  • 中间值：mid = left + (right - left) / 2
  • 缩小范围：
    • 如果 arr[mid] < target，左边更新为 mid + 1（mid 已经排除）
    • 如果 arr[mid] > target，右边更新为 mid - 1（mid 已经排除）

为什么不用 (left + right) / 2？
因为当 left 和 right 很大时（比如接近 2³¹ - 1），left + right 可能会超过 int 的最大值，导致溢出变成负数。而 left + (right - left) / 2 保证加法不会溢出，即使数组有上亿个元素也没问题。

新手易犯的错误

  1. 忘记数组要有序
    如果数组是无序的，二分查找就没法用——因为中间元素的大小不能告诉你是向左还是向右找。必须先用 sort 排序。

  2. 死循环
    比如当你用左闭右开区间时，更新边界写错（例如 left = mid 而 mid 可能等于 left），就可能陷入死循环。永远记住：每次缩小范围时，一定要让区间 严格变小。

  3. 返回值理解错误
    二分查找返回的是下标（从 0 开始）。如果数组中有多个相同的值，普通的二分查找只返回其中一个，不一定是第一个或最后一个。要想找第一个或最后一个，需要对二分查找进行变形（叫“二分查找边界”）。

  4. mid 计算错误
    有人写成 mid = (left + right) / 2，这在大多数情况下没问题，但为了安全，建议养成用 left + (right - left) / 2 的习惯。

  5. 忘记处理空数组
    如果数组长度为 0，right = -1，循环条件 left <= right 会直接不执行，返回 -1，没问题。但如果手写时没考虑，可能数组越界。

完整可运行示例（包含多个测试）

下面是一个完整的程序，你可以在自己的电脑上编译运行，测试不同情况：

#include <iostream>
#include <vector>
using namespace std;

// 二分查找（左闭右闭）
int binarySearch(vector<int>& arr, int target) {
    int left = 0;                     // 左边界
    int 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; // 没找到
}

int main() {
    // 测试1：正常情况
    vector<int> scores = {60, 65, 70, 75, 80, 85, 90, 95, 100};
    int target = 85;
    int idx = binarySearch(scores, target);
    if (idx != -1) {
        cout << "成绩 " << target << " 在数组中的下标是 " << idx << endl;
    } else {
        cout << "成绩 " << target << " 不存在" << endl;
    }

    // 测试2：查找第一个元素
    cout << "查找 60: " << binarySearch(scores, 60) << endl; // 应输出 0

    // 测试3：查找最后一个元素
    cout << "查找 100: " << binarySearch(scores, 100) << endl; // 应输出 8

    // 测试4：查找不存在的值
    cout << "查找 72: " << binarySearch(scores, 72) << endl; // 应输出 -1

    // 测试5：空数组
    vector<int> empty;
    cout << "空数组查找 5: " << binarySearch(empty, 5) << endl; // 应输出 -1

    return 0;
}

输出结果：

成绩 85 在数组中的下标是 5
查找 60: 0
查找 100: 8
查找 72: -1
空数组查找 5: -1

总结与延伸

二分查找虽然代码简单，但 边界细节决定成败。建议初学者先背熟一种写法（比如左闭右闭），然后多做几道题目巩固。

相关知识点指引：

  • 二分查找的变种：查找第一个等于目标的位置、最后一个等于目标的位置、第一个大于等于目标的位置——这些在 CSP-J 中也很常见。
  • 二分答案：不是直接在数组中查找，而是通过二分的思路在可能的答案范围内找最优解（比如最小化最大值、最大化最小值）。这是更高级的用法，常结合 check 函数使用。
  • 排序算法：二分查找依赖有序数组，所以需要掌握排序（如 sort 函数或快速排序原理）。
  • 时间复杂度与空间复杂度：学会分析二分查找的 O(log n) 复杂度，能帮你判断算法是否高效。

如果你学会了普通二分查找，下一步可以挑战 在旋转有序数组中查找（比如 [4,5,6,7,0,1,2] 中找 3），那就要加上更多判断，但核心思想还是二分。

加油，二分查找是竞赛路上的第一把利器，熟练掌握它，后面的路会顺很多！

例题精讲

1单选题

二分查找算法能够正确执行的前提条件是什么？

A数据必须是有序的
B数据必须是无序的
C数据必须是整数类型
D数据必须连续存储在内存中
2判断题

二分查找算法的时间复杂度是O(log n)，其中n为数据规模。

3填空题
以下函数在升序数组arr中查找target，返回下标（不存在返回-1）。请补全计算中间位置的语句。

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (___ - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
4单选题

在有序数组 [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] 中查找数字 38，第一次比较的是哪个元素？

A5
B12
C16
D23
5判断题

二分查找算法可以直接应用于无序链表。