lower_bound、upper_bound 和 last_less_equal。它们的作用是在 有序数组 中查找目标值的位置。下面是对每个函数的详细解释：
1. lower_bound 函数
功能：
在有序数组 a 中查找第一个 大于或等于 target 的元素的位置。
参数：
a[]：有序数组。n：数组的长度。target：目标值。
实现逻辑：
- 初始化左边界
l = 0，右边界r = n - 1。 - 使用二分查找：
- 计算中间位置
mid = l + (r - l) / 2。 - 如果
a[mid] >= target，说明目标值在左半部分，更新右边界r = mid。 - 否则，目标值在右半部分，更新左边界
l = mid + 1。
- 计算中间位置
- 最终返回
l，即第一个大于或等于target的位置。
示例：
int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
int pos = lower_bound(a, n, target); // 返回 2
2. upper_bound 函数
功能：
在有序数组 a 中查找第一个 大于 target 的元素的位置。
参数：
a[]：有序数组。n：数组的长度。target：目标值。
实现逻辑：
- 初始化左边界
l = 0，右边界r = n - 1。 - 使用二分查找：
- 计算中间位置
mid = l + (r - l) / 2。 - 如果
a[mid] > target，说明目标值在左半部分，更新右边界r = mid。 - 否则，目标值在右半部分，更新左边界
l = mid + 1。
- 计算中间位置
- 最终返回
l，即第一个大于target的位置。
示例：
int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
int pos = upper_bound(a, n, target); // 返回 3
3. last_less_equal 函数
功能：
在有序数组 a 中查找最后一个 小于或等于 target 的元素的位置。
参数：
a[]：有序数组。n：数组的长度。target：目标值。
实现逻辑：
- 调用
upper_bound函数，找到第一个大于target的位置。 - 返回
upper_bound(a, n, target) - 1，即最后一个小于或等于target的位置。
示例：
int a[] = {1, 3, 5, 7, 9};
int n = 5;
int target = 5;
int pos = last_less_equal(a, n, target); // 返回 2
4. 总结
lower_bound：查找第一个 大于或等于target的位置。upper_bound：查找第一个 大于target的位置。last_less_equal：查找最后一个 小于或等于target的位置。
这些函数在有序数组中非常有用，常用于解决 查找问题 或 范围查询问题。
5. 完整代码
#include <iostream>
using namespace std;int lower_bound(int a[], int n, int target) {int l = 0, r = n - 1;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] >= target) r = mid;else l = mid + 1;}return l;
}int upper_bound(int a[], int n, int target) {int l = 0, r = n - 1;while (l < r) {int mid = l + (r - l) / 2;if (a[mid] > target) r = mid;else l = mid + 1;}return l;
}int last_less_equal(int a[], int n, int target) {return upper_bound(a, n, target) - 1;
}int main() {int a[] = {1, 3, 5, 7, 9};int n = 5;int target = 5;cout << "lower_bound: " << lower_bound(a, n, target) << endl; // 输出 2cout << "upper_bound: " << upper_bound(a, n, target) << endl; // 输出 3cout << "last_less_equal: " << last_less_equal(a, n, target) << endl; // 输出 2return 0;
}
6. 适用场景
- 查找问题：在有序数组中查找目标值的位置。
- 范围查询：查找满足某个条件的元素范围。
- 插入位置：确定目标值在有序数组中的插入位置。
这些函数是二分查找的经典应用，理解它们有助于解决许多算法问题。
