20260228 143122 Cpp 入门第十六课

第十六章：二分查找——快如闪电的查找方法 ¶

你好！欢迎来到第十六章！在前面的章节，我们学习了顺序查找——从第一个元素开始一个一个找，就像在一堆书里一本一本翻。但如果书已经按编号排好序了，我们还有更快的办法：先看中间那本，如果目标编号比中间的小，就去左边找；如果大，就去右边找。这样每次都能排除一半的书，这就是二分查找（也叫折半查找）。这一章我们就来学习这种高效的查找算法！

16.1 二分查找程序范例 ¶

假设我们有一个已经按升序排好的数组，要查找某个数是否在数组中，如果在，返回它的下标。

#include <iostream>
using namespace std;

// 二分查找函数，返回下标，没找到返回-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;   // 中间位置，防止溢出
        if (arr[mid] == target) {
            return mid;     // 找到了，返回下标
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标在右半部分
        } else {
            right = mid - 1;// 目标在左半部分
        }
    }
    return -1;              // 没找到
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target;
    cout << "请输入要查找的数：";
    cin >> target;

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

运行示例（输入7）：

请输入要查找的数：7
找到了，下标是：3

运行示例（输入6）：

请输入要查找的数：6
没找到

16.2 二分查找的用法 ¶

16.2.1 二分查找的思想 ¶

二分查找就像猜数字游戏：对方想一个1-100之间的数，你每次猜中间的数，对方告诉你“大了”或“小了”，你就能排除一半的数字。这样最多猜7次就能猜到（因为2^7=128>100）。这就是二分查找的核心：每次把查找范围缩小一半。

适用条件：数组必须是有序的（升序或降序）。如果数组无序，必须先排序才能用二分查找。

16.2.2 二分查找的步骤 ¶

确定查找范围的左边界 left 和右边界 right（通常初始为0和n-1）。
当 left <= right 时：
- 计算中间位置 mid = left + (right - left) / 2。
- 如果 arr[mid] == target，找到，返回 mid。
- 如果 arr[mid] < target，说明目标在右半部分，更新 left = mid + 1。
- 如果 arr[mid] > target，说明目标在左半部分，更新 right = mid - 1。
如果循环结束还没找到，返回-1。

16.2.3 二分查找的代码实现 ¶

我们已经看到了迭代版本。也可以用递归实现：

int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left > right) return -1;   // 没找到
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, right, target);
    } else {
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

调用时：binarySearchRecursive(arr, 0, n-1, target);

16.2.4 注意事项 ¶

计算mid：用 left + (right - left) / 2 而不是 (left + right) / 2，防止 left+right 太大导致溢出。
边界条件：循环条件 left <= right 要小心，如果写成 < 可能漏掉最后一个元素。
数组必须有序：如果数组无序，结果不可预测。

16.2.5 二分查找的变种 ¶

有时候我们需要找的不是精确等于某个值的下标，而是满足某种条件的边界。比如：
- 找第一个等于target的位置
- 找最后一个等于target的位置
- 找第一个大于等于target的位置
- 找最后一个小于等于target的位置

这些变种在STL中对应 lower_bound 和 upper_bound，我们也可以自己实现。

16.3 编程实例讲解 ¶

实例1：找第一个等于target的位置 ¶

当数组中有重复元素时，我们要找第一次出现的位置。

int firstOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;      // 记录找到的位置
            right = mid - 1;   // 继续在左边找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

实例2：找最后一个等于target的位置 ¶

int lastOccurrence(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            result = mid;
            left = mid + 1;    // 继续在右边找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

实例3：找第一个大于等于target的位置（即 lower_bound）¶

int lowerBound(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    int result = n;   // 如果所有数都小于target，返回n（表示不存在）
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

实例4：在一个旋转有序数组中查找（选做）¶

题目：一个升序数组在某个点被旋转了，比如 [4,5,6,7,0,1,2]，在这个数组中查找某个数。

思路：先判断哪一半是有序的，然后根据target是否在有序部分来缩小范围。

int searchRotated(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        // 左半部分有序
        if (arr[left] <= arr[mid]) {
            if (target >= arr[left] && target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } 
        // 右半部分有序
        else {
            if (target > arr[mid] && target <= arr[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

16.4 阶段性编程练习 ¶

练习1：在有序数组 [2, 5, 8, 12, 16, 23, 38, 45, 56, 72] 中查找数字 23 和 50，分别输出结果。
练习2：编写一个函数，用二分查找求一个数的平方根（整数部分）。例如输入10，返回3（因为3²=9≤10，4²=16>10）。提示：在0到x之间二分查找。
练习3：在一个有序数组中，找第一个大于 target 的位置（即 upper_bound）。
练习4：在一个有序数组中，统计某个数出现的次数（可以用 firstOccurrence 和 lastOccurrence 计算）。
练习5：用递归实现二分查找，并在主函数中测试。