lower_bound(a)

`lower_bound()`是C++ STL中的一个函数，用于在有序序列中查找第一个大于等于给定值的元素的位置。具体用法如下：

假设有一个有序数组`a`，要查找第一个大于等于`x`的元素的位置，可以使用以下代码：

int pos = lower_bound(a, a + n, x) - a;

其中，`n`为数组`a`的长度，`x`为要查找的值，`pos`为查找结果，即第一个大于等于`x`的元素在数组`a`中的下标。如果数组中不存在大于等于`x`的元素，则返回`n`。

需要注意的是，`lower_bound()`函数的时间复杂度为$O(logn)$，只适用于有序序列。

相关问题

lower_bound

The lower_bound() function is a built-in C++ function that returns an iterator pointing to the first element in a sorted range that is not less than a given value. It is defined in the <algorithm> header file.

Syntax:

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

Here, first and last are iterators that define the range to be searched, and val is the value to be compared with the elements in the range.

The lower_bound() function works only on sorted ranges. It uses a binary search algorithm to find the first element that is not less than val. If such an element is found, it returns an iterator to that element. If no such element is found, it returns an iterator to the end of the range.

Example:

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

int main() {
    std::vector<int> v {1, 3, 5, 7, 9};

    auto it = std::lower_bound(v.begin(), v.end(), 6);

    if (it != v.end()) {
        std::cout << "The first element not less than 6 is " << *it << '\n';
    } else {
        std::cout << "No element not less than 6 was found\n";
    }

    return 0;
}

Output:

The first element not less than 6 is 7

map lower_bound

和upper_bound的功能和使用方式是什么？

lower_bound和upper_bound是std::map容器中的两个函数，用于查找满足特定条件的元素的位置。lower_bound函数返回一个指向第一个不小于指定键值的元素的迭代器，而upper_bound函数返回一个指向第一个大于指定键值的元素的迭代器。

以一个例子来说明它们的使用方式，假设有一个map容器mp，其中存储了一些键值对。我们可以通过以下代码示例来理解lower_bound和upper_bound的用法：

map<int, string> mp;
mp = "a";
mp = "b";
mp = "c";
mp = "d";

map<int, string>::iterator p1, p2;
p1 = mp.lower_bound(3); // p1指向键值为3的元素，即p1->second == "b"
p2 = mp.upper_bound(3); // p2指向键值为5的元素，即p2->second == "c"

p1 = mp.lower_bound(9); // p1指向mp.end()，因为容器中没有键值为9的元素
p2 = mp.upper_bound(9); // p2指向mp.end()，因为容器中没有键值为9的元素

如果lower_bound和upper_bound找不到满足条件的元素，它们会返回指向容器末尾的迭代器，即map.end()。这意味着在容器内所有节点都比指定键值小的情况下，lower_bound和upper_bound都会返回map.end()，而在容器内所有节点都比指定键值大的情况下，lower_bound会返回map.begin()，而upper_bound会返回map.end()。