C++ algorithm lower_bound()

2024年8月30日 | 阅读4分钟

C++ algorithm 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 之间的距离上呈对数关系：执行最多 log₂ (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'.

下一主题C++ 算法

C++ algorithm lower_bound()

语法

参数

返回值

复杂度

数据竞争

异常

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

示例 1

示例 2

示例 3

示例 4

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ algorithm lower_bound()

语法

参数

返回值

复杂度

数据竞争

异常

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

示例 1

示例 2

示例 3

示例 4

相关帖子

algorithm generate() 函数

algorithm includes() 函数

algorithm reverse() 函数

algorithm replace_copy_if() 函数

algorithm random_shuffle() 函数

algorithm generate_n() 函数

algorithm partition() 函数

algorithm copy_backward() 函数

algorithm none_of() 函数