lower_boundupper_bound-和-last_less_equal
目录
lower_bound、upper_bound 和 last_less_equal
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; // 输出 2
cout << "upper_bound: " << upper_bound(a, n, target) << endl; // 输出 3
cout << "last_less_equal: " << last_less_equal(a, n, target) << endl; // 输出 2
return 0;
}6. 适用场景
- 查找问题 ：在有序数组中查找目标值的位置。
- 范围查询 ：查找满足某个条件的元素范围。
- 插入位置 ：确定目标值在有序数组中的插入位置。
这些函数是二分查找的经典应用，理解它们有助于解决许多算法问题。