二分查找的“亲戚们”：不止找精确值，还能找边界

你已经学会用二分查找在一个有序数组里快速找到某个数字。但实际生活中，我们常常需要的不只是“有没有”，而是“第一个符合条件的”或“最后一个符合条件的”。比如：

老师把全班成绩按从低到高排好，想快速找出第一个及格（≥60分）的同学在第几个位置。
超市里的商品价格从小到大排列，你想知道最后一个不超过10元的东西是什么。
游戏里玩家积分排名，你想找出最后一个拿到“优秀”称号（比如积分≥1000）的玩家在哪里。

这些问题都能用二分查找的“变种”轻松解决。它们的思想和基础二分查找一模一样，只是判断条件和边界移动稍微改一改。

1. 第一个 ≥ 目标值的位置（lower_bound）

这是最常用的变种，也叫“下界”。它返回数组中第一个 大于等于 某个数的索引。如果所有数都小于目标值，则返回数组长度（表示没找到）。

生活例子：成绩单 [45, 55, 58, 60, 62, 70, 80]，要找第一个≥60的同学。答案是索引3（值为60）。就算有重复的60，也要返回最左边那个。

算法思路：用二分，中间值 arr[mid] 如果小于目标值，说明要找的位置在右边，左边界右移；否则（≥目标值），说明当前位置可能是答案，但左边可能还有更小的，所以右边界缩小到 mid。

代码实现（保留原有，加详细注释）：

#include <iostream>
using namespace std;

// 返回第一个 >= target 的索引，如果所有数都小于 target，返回 n
int lowerBound(int arr[], int n, int target) {
    int left = 0;          // 左边界，包含
    int right = n;         // 右边界，不包含（表示有效范围 [left, right)）
    while (left < right) { // 当区间不为空
        int mid = left + (right - left) / 2;  // 防溢出写法
        if (arr[mid] < target) {
            left = mid + 1;   // mid 太小，答案在右边
        } else {
            right = mid;      // mid >= target，答案在左边（包括 mid）
        }
    }
    return left; // left == right，就是第一个 >= target 的位置
}

int main() {
    int arr[] = {45, 55, 58, 60, 62, 70, 80};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 60;

    int pos = lowerBound(arr, n, target);
    if (pos < n) {
        cout << "第一个 ≥" << target << " 的元素在索引" << pos 
             << "，值为" << arr[pos] << endl;
    } else {
        cout << "所有元素都小于" << target << endl;
    }
    return 0;
}

输出：第一个 ≥60 的元素在索引3，值为60

2. 第一个 > 目标值的位置（upper_bound）

也叫“上界”，返回第一个 严格大于 目标值的索引。如果所有数都 ≤ 目标值，则返回数组长度。

生活例子：还是成绩单，想找第一个成绩大于60的同学（也就是超过及格线的第一个）。答案是索引4（值为62）。

思路：和 lower_bound 很像，只是把 arr[mid] < target 改成 arr[mid] <= target——因为等于时要继续向右找。

代码：

// 返回第一个 > target 的索引，如果不存在返回 n
int upperBound(int arr[], int n, int target) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {   // 注意这里是 <=
            left = mid + 1;         // 中间值太小或等于，向右找
        } else {
            right = mid;            // 中间值 > target，向左缩
        }
    }
    return left;
}

3. 最后一个 ≤ 目标值的位置

这个可以用 upper_bound 的结果减1 得到。因为所有 ≤ target 的元素，都在第一个 > target 的元素之前。

生活例子：找最后一个不及格（<60）的同学。先找第一个 ≥60 的位置（lower_bound是3），那么最后一个 <60 的位置就是 3-1=2，值为58。

通用公式：

最后一个 ≤ target 的位置 = upperBound(arr, n, target) - 1
如果结果是 -1，说明所有数都 > target。

注意：需要检查结果是否 ≥0，否则越界。

4. 最后一个等于目标值的位置

这个可以用两次二分：先找第一个 ≥ target 的位置，再找第一个 > target 的位置，如果它们指向同一个区间（即 lowerBound == upperBound），说明没有这个值；否则最后一个等于 target 的位置是 upperBound - 1。

例子：数组 [1, 2, 2, 2, 3]，target=2。

lower_bound 返回索引1（第一个≥2）
upper_bound 返回索引4（第一个>2）
区间 [1, 4) 都是2，最后一个等于2的是索引3。

代码：

// 返回最后一个等于 target 的索引，不存在返回 -1
int lastEqual(int arr[], int n, int target) {
    int first = lowerBound(arr, n, target);
    int lastPos = upperBound(arr, n, target) - 1;
    // 检查 first 是否在数组内且 arr[first] == target
    if (first < n && arr[first] == target) {
        return lastPos;   // 肯定 >= first
    }
    return -1;
}

5. 新手容易犯的错误

右边界搞错：用 right = n-1 还是 right = n？如果右边界用 n-1，那么循环条件要改成 left <= right，且边界移动也要相应调整。我推荐统一用 左闭右开 区间（[left, right)），这样代码更简洁，不容易出现死循环。
死循环：当 left + 1 == right 时， mid = left，如果判断条件没有正确移动边界，可能死循环。例如有些变种用 left = mid 而不是 left = mid+1，很容易卡住。记住：左边界有 +1，右边界没有 +1，这个规律可以防止死循环。
没考虑找不到的情况：返回结果等于 n 时，说明所有数都小于/大于 target，此时如果直接用 arr[pos] 会数组越界。一定要先检查 pos < n。
混淆 upper_bound 和 lower_bound：upper_bound 返回的是 第一个大于，不是最后一个小于等于。要得到最后一个小于等于，记得减1。

6. 完整示例：成绩查询工具箱

下面把上面几个函数整合到一起，模拟老师查询成绩的需求。

#include <iostream>
using namespace std;

// 函数声明
int lowerBound(int arr[], int n, int target);  // 第一个 >=
int upperBound(int arr[], int n, int target);  // 第一个 >
int lastEqual(int arr[], int n, int target);   // 最后一个等于

int main() {
    // 全班成绩（已排序）
    int scores[] = {45, 55, 58, 60, 60, 62, 70, 80};
    int n = sizeof(scores) / sizeof(scores[0]);

    // 1. 找第一个及格的（≥60）
    int p1 = lowerBound(scores, n, 60);
    if (p1 < n) {
        cout << "第一个及格的同学在索引 " << p1 
             << "，分数 " << scores[p1] << endl;
    } else {
        cout << "没有同学及格" << endl;
    }

    // 2. 找最后一个不及格的（<60），等价于最后一个 ≤59
    int p2 = upperBound(scores, n, 59) - 1;
    if (p2 >= 0) {
        cout << "最后一个不及格的同学在索引 " << p2 
             << "，分数 " << scores[p2] << endl;
    } else {
        cout << "全部及格" << endl;
    }

    // 3. 找最后一个得60分的同学（60有重复）
    int p3 = lastEqual(scores, n, 60);
    if (p3 != -1) {
        cout << "最后一个得60分的同学在索引 " << p3 
             << "，分数 " << scores[p3] << endl;
    } else {
        cout << "没有人得60分" << endl;
    }

    return 0;
}

// 实现 lowerBound
int lowerBound(int arr[], int n, int target) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// 实现 upperBound
int upperBound(int arr[], int n, int target) {
    int left = 0, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// 实现 lastEqual
int lastEqual(int arr[], int n, int target) {
    int first = lowerBound(arr, n, target);
    // 先判断 target 是否存在
    if (first == n || arr[first] != target) {
        return -1;
    }
    return upperBound(arr, n, target) - 1;
}

输出：

第一个及格的同学在索引 3，分数 60
最后一个不及格的同学在索引 2，分数 58
最后一个得60分的同学在索引 4，分数 60

7. 相关知识点指引

基础二分查找：先熟练掌握在有序数组中找一个确切值的程序，理解“左闭右开”区间和边界移动原则。
C++ STL 中的现成函数：
- lower_bound 和 upper_bound 在头文件 <algorithm> 中。
  用法：int *pos = lower_bound(arr, arr+n, target); 返回指针，用 pos - arr 得到索引。
  学会直接用 STL 可以省去手写代码的麻烦，但理解原理更重要。
搜索旋转排序数组：这是二分查找的进阶应用，数组不是完全有序但可以分两段。
二分答案：当问题不是直接查找数组元素，而是查找某个符合条件的最值（比如“最小速度”、“最大负重”）时，也可以用二分思想。

掌握了这些二分查找的“亲戚们”，你就能像切西瓜一样快速切出有序数组中的任何一块，解决更多有趣的搜索问题。试着用它们去分析自己的考试成绩排名吧！

C++二分查找经典问题