C++ 算法 lower_bound()函数

C++算法 lower_bound() 函数是二分搜索的版本。该函数用于返回一个指向有序范围[first, last)中第一个不小于（即大于或等于）指定值 val 的迭代器。

第一个版本使用运算符 < 来比较元素，第二个版本使用 comp 函数。

语法

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

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

参数

first ：一个前向迭代器，指向要搜索的范围的第一个元素。

last ：一个前向迭代器，指向要搜索的范围的最后一个元素之后的位置。

comp ：一个用户定义的二元谓词函数，接受两个参数并返回true（如果两个参数有序）或false。它遵循严格弱排序来对元素排序。

val ：要比较范围中的元素的下界值。

返回值

如果找不到该元素，它返回一个指向范围中第一个不小于val的元素的迭代器，如果没有这样的元素，则返回last。

复杂性

平均情况下，复杂度在first和last之间的距离的对数级别：执行最多log2(N) + 1次元素比较，其中N = last – first。

数据竞争

[first, last)范围内的对象被访问。

异常

如果元素比较或迭代器操作引发异常，此函数会抛出异常。

注意：无效参数会导致未定义行为。

示例1

让我们看一个简单的示例来演示lower_bound()的使用：

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

using namespace std;

int main()
{

  vector<int> v = {3, 1, 4, 6, 5};


  decltype(v)::iterator it = lower_bound(v.begin(), v.end(), 4);

  cout << *it << ", pos = " << (it - v.begin()) << endl;
  return 0;

}

输出:

4, pos = 2

示例2

让我们来看另一个简单的示例：

#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

using namespace std;

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

  sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  vector<int>::iterator low,up;
  low=lower_bound (v.begin(), v.end(), 20); //          ^
  up= upper_bound (v.begin(), v.end(), 20); //                   ^

  cout << "lower_bound at position " << (low- v.begin()) << '\n';
  cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

输出：

lower_bound at position 3
upper_bound at position 6

示例3

让我们看一个另外的简单示例：

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

using namespace std;

template<class ForwardIt, class T, class Compare=less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first: last;
}

int main() 
{
    vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

    auto lower = lower_bound(data.begin(), data.end(), 4);
    auto upper = upper_bound(data.begin(), data.end(), 4);

    copy(lower, upper, ostream_iterator<int>(cout, " "));

    cout << '\n';

    // classic binary search, returning a value only if it is present

    data = { 1, 2, 4, 6, 9, 10 }; 

    auto it = binary_find(data.cbegin(), data.cend(), 4); //< choosing '5' will return end()

    if(it != data.cend())
      cout << *it << " found at index "<< distance(data.cbegin(), it);

    return 0;
}

输出：

4 4 4 
4 found at index 2

示例4

让我们再看一个简单的示例：

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

using namespace std;

bool ignore_case(char a, char b) {
   return(tolower(a) == tolower(b));
}

int main(void) {
   vector<char> v = {'A', 'b', 'C', 'd', 'E'};
   auto it = lower_bound(v.begin(), v.end(), 'C');

   cout << "First element which is greater than \'C\' is " << *it << endl;

   it = lower_bound(v.begin(), v.end(), 'C', ignore_case);

   cout << "First element which is greater than \'C\' is " << *it << endl;

   it = lower_bound(v.begin(), v.end(), 'z', ignore_case);

   cout << "All elements are less than \'z\'." << endl;

   return 0;
}

输出：

First element which is greater than 'C' is b
First element which is greater than 'C' is d
All elements are less than 'z'.