lower_bound函数返回下标

lower_bound函数是C++标准库中的一个算法，用于在有序的容器（如数组或向量）中查找大于或等于给定值的第一个元素的位置（下标）。

它的使用方法如下：

#include <algorithm>
// ...
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 3;
int* lower = std::lower_bound(arr, arr + n, key);

在上述示例中，lower_bound函数会在arr数组中查找大于或等于key的第一个元素的位置，并将其迭代器返回给指针lower。如果不存在这样的元素，则返回容器末尾的迭代器。

需要注意的是，lower_bound函数只适用于有序容器。如果容器未排序，则结果是不确定的。此外，lower_bound函数也可用于自定义比较函数的容器，例如使用自定义的比较函数对象或lambda表达式。

相关问题

让库函数lower_bound返回数组下标

lower_bound是C++标准库中的一个函数，用于在有序数组中查找第一个大于或等于给定值的元素的位置。它返回一个迭代器，指向数组中第一个大于或等于给定值的元素。

要让lower_bound返回数组下标，可以通过对返回的迭代器进行减法操作来计算下标。具体步骤如下：

1. 首先，需要确保数组是有序的。
2. 调用lower_bound函数，传入数组的起始迭代器和结束迭代器，以及要查找的值作为参数。
3. lower_bound返回一个迭代器，指向第一个大于或等于给定值的元素。
4. 使用返回的迭代器减去数组的起始迭代器，即可得到该元素在数组中的下标。

下面是一个示例代码：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 6;

    auto it = std::lower_bound(arr.begin(), arr.end(), target);
    int index = std::distance(arr.begin(), it);

    std::cout << "The index of the first element greater than or equal to " << target << " is: " << index << std::endl;

    return 0;
}

输出结果为：

The index of the first element greater than or equal to 6 is: 5

lower_bound和upper_bound函数实际演示

假设有一个已经排好序的vector：

vector<int> nums = {1, 3, 3, 5, 7, 9};

我们可以使用lower_bound和upper_bound函数来查找某个元素在该vector中的位置。

lower_bound函数：

auto it = lower_bound(nums.begin(), nums.end(), 3);
cout << it - nums.begin() << endl; // 1

这里的lower_bound函数返回一个迭代器，指向第一个大于等于3的元素。因此，它返回的迭代器指向的是3，它在vector中的下标为1。

如果要查找的元素在vector中不存在，lower_bound函数也能返回该元素应该插入的位置：

auto it2 = lower_bound(nums.begin(), nums.end(), 4);
cout << it2 - nums.begin() << endl; // 3

这里的lower_bound函数返回一个迭代器，指向第一个大于等于4的元素。由于vector中没有4，所以它返回的迭代器指向的是5，它在vector中的下标为3。

upper_bound函数：

auto it3 = upper_bound(nums.begin(), nums.end(), 3);
cout << it3 - nums.begin() << endl; // 3

这里的upper_bound函数返回一个迭代器，指向第一个大于3的元素。因此，它返回的迭代器指向的是5，它在vector中的下标为3。

如果要查找的元素在vector中不存在，upper_bound函数也能返回该元素应该插入的位置：

auto it4 = upper_bound(nums.begin(), nums.end(), 4);
cout << it4 - nums.begin() << endl; // 3

这里的upper_bound函数返回一个迭代器，指向第一个大于4的元素。由于vector中没有4，所以它返回的迭代器指向的是5，它在vector中的下标为3。

综上所述，lower_bound和upper_bound函数可以帮助我们快速查找某个元素在已排序的容器中的位置。