一招秒杀查找问题：二分查找

你有没有玩过“猜数字”游戏？朋友心里想一个1到100之间的数，你每次猜一个，他告诉你“大了”或“小了”。如果你从1开始挨个猜，最多要猜100次。但如果你每次猜中间的数——先猜50，他如果说“大了”，你就知道数字在1~49之间；再猜25……这样每次都能排除一半的可能性，最多猜7次就能找到答案（因为2⁷=128＞100）。这种每次排除一半可能性的聪明方法，就是二分查找（Binary Search）。

二分查找专门用来在已经排好序的数据中快速找到目标值。比如，在按从小到大排列的成绩单里找你的分数，在按字母顺序排列的字典里查某个单词，或者在一堆按价格排序的零食中找一种特定的零食——都可以用二分查找，一找一个准。

二分查找的三个关键步骤

二分查找的原理很简单，就像猜数字一样，每次取当前范围的中间值比较。

确定查找范围：一开始，整个数组就是范围。用两个变量标记范围的两端：左边界 left（第一个元素的位置）和右边界 right（最后一个元素的位置）。
取中间值比较：计算中间位置 mid，拿 arr[mid] 和目标值 target 做比较。
- 如果相等，恭喜你，找到了！
- 如果 arr[mid] < target，说明目标值在右边，那么把左边界 left 移到 mid + 1。
- 如果 arr[mid] > target，说明目标值在左边，把右边界 right 移到 mid - 1。
重复第二步，直到 left > right（范围空了），说明没找到。

生活中的例子：找零食价格

假设你有一张按价格从小到大排列的零食清单（下图）。你想找一种价格是 23 元的零食，用二分查找会怎样？

索引	0	1	2	3	4	5	6	7	8	9
价格	2	5	8	12	16	23	38	45	56	72

第一次：left = 0，right = 9，中间位置 mid = 4，价格 16 元。16 < 23，所以目标在右边，left 更新为 5。
第二次：left = 5，right = 9，中间位置 mid = 7，价格 45 元。45 > 23，目标在左边，right 更新为 6。
第三次：left = 5，right = 6，中间位置 mid = 5，价格 23 元。找到了！

只用了 3 次比较，如果从头到尾一个个查，要查 6 次。数据量越大，二分查找的优势就越明显。

二分查找的代码实现

下面用 C++ 写一个通用的二分查找函数。注意代码里每一行变量都加了中文注释，方便理解。

#include <iostream>
using namespace std;

// 二分查找函数：在有序数组 arr 中查找目标值 target
// arr: 数组名
// n: 数组长度
// target: 要查找的值
// 返回值：目标值的索引（从0开始），如果找不到则返回 -1
int binarySearch(int arr[], int n, int target) {
    int left = 0;          // 左边界（第一个元素索引）
    int right = n - 1;     // 右边界（最后一个元素索引）

    while (left <= right) {                       // 当范围还有效时继续
        int mid = left + (right - left) / 2;      // 计算中间位置，防止 (left+right) 溢出

        if (arr[mid] == target) {                // 正好找到
            return mid;
        } else if (arr[mid] < target) {          // 目标在右边，缩小左边界
            left = mid + 1;
        } else {                                 // 目标在左边，缩小右边界
            right = mid - 1;
        }
    }
    return -1; // 循环结束还没找到，说明不存在
}

int main() {
    // 一个从小到大排好序的零食价格数组
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72};
    int n = sizeof(arr) / sizeof(arr[0]);   // 计算数组长度

    int target = 23;                        // 想找的零食价格

    int result = binarySearch(arr, n, target);
    if (result != -1) {
        cout << "找到了！索引是: " << result << endl;
    } else {
        cout << "没找到" << endl;
    }
    return 0;
}

运行结果：

找到了！索引是: 5

新手最容易犯的四个错误

错误1：忘记数据必须有序

二分查找的前提是数据已经排好序。如果你在一个乱序的数组上使用二分查找，就像在打乱的字典里查单词，结果会完全错误。使用前一定要先排序（可以用 sort 或手动排序）。

错误2：边界条件写错成 `left < right`

很多同学在 while 循环里写 left < right，这会导致当搜索范围只剩下一个元素时（left == right），循环直接结束，漏掉最后一个元素。记住：while (left <= right) 才能覆盖所有情况。

错误3：更新边界时忘了加1或减1

比如找到中间值发现 arr[mid] < target，应该把 left 更新为 mid + 1（因为 mid 已经比较过，肯定不是目标）。如果错误地写成 left = mid，就可能陷入死循环。同样，right 要更新为 mid - 1。

错误4：计算中间位置时直接 `(left + right) / 2`

如果 left 和 right 都很大（比如接近数组的极限 INT_MAX），它们的和可能超出 int 范围，导致溢出。使用 left + (right - left) / 2 是安全的做法，结果和 (left+right)/2 一样，但不会溢出。

完整可运行的示例：查找考试成绩

下面是一个更贴近学生生活的例子：老师按分数从低到高发布了考试成绩单（数组），你想快速找到自己的分数（比如 88 分）在不在名单里，如果在，在第几个位置？

#include <iostream>
using namespace std;

// 二分查找函数（同上）
int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 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() {
    // 全班考试成绩（从小到大排好序）
    int scores[] = {55, 62, 68, 73, 78, 82, 88, 91, 95, 99};
    int n = sizeof(scores) / sizeof(scores[0]);

    int myScore = 88;                    // 你要查找的分数
    int index = binarySearch(scores, n, myScore);

    if (index != -1) {
        cout << "你的分数 " << myScore << " 分，排在班级第 " 
             << index + 1 << " 名（按分数从低到高）" << endl;
    } else {
        cout << "你的分数 " << myScore << " 不在名单中" << endl;
    }
    return 0;
}

二分查找的“亲戚”

掌握基础二分查找后，你还可以认识它的几个“变种”：

查找第一个大于等于目标值的位置（lower_bound）：比如在成绩单里找第一个及格（60分）的位置。
查找第一个大于目标值的位置（upper_bound）：比如找第一个超过90分的同学。
在旋转有序数组中查找：比如数组本来有序，但被“旋转”过（例如 [4,5,6,7,0,1,2]），仍然可以用二分查找的思想。
二分答案：不只是查找数字，还可以用二分法猜测问题的答案，比如“最多能分成几组？”“最短时间是多少？”。

另外，如果你学完了排序算法（比如冒泡排序、快速排序），就能自己先排序再二分，完成“先整理，再快速查找”的全套操作。

总结

二分查找就像玩游戏一样，每次从中间猜，快速排除一半可能性。它要求数据有序，时间复杂度只有 O(log n) —— 即便有10亿条数据，也只需要30次左右比较。下次你要在大量有序数据中找东西时，别忘了这个超级好用的方法！

C++二分查找算法