【C++】 详解 lower

目录

一、前言

二、函数详解 

🥝 lower_bound

🍍upper_bound

 三、常考面试题

 四、共勉

一、前言

这两个函数是我在 LeetCode 上做题见到，看到不熟悉的函数 lower_bound 和 upper_bound让我感觉很难受，于是在 C++ 官网去学习，例子就一个是最基础的，我看明白了。虽然是两个函数的接口就两个，但是有时候看别人使用的时候，里面参数还可以放不同的仿函数，我懵逼了。就去网上搜，但是大家讲解的都是它的第一个接口。我只能再把文档一遍一遍过，代码一遍遍的尝试，调试。最终通过查阅资料将其总结如下。

二、函数详解 

        首先，大家都说用这两个函数之前必须是在有序的数组中，但是都没有说明为什么是在有序的数组，因为他们的底层实现是二分查找（这个也是我在别人的题解的时候知道的）。如果对二分查找有不清楚的伙伴可以看看这篇文章：详解二分查找

 🥝 lower_bound

 函数原型：

原型1：

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

 原型2：

template 
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val, Compare comp);

模板参数解释：

1. ForwardIterator就是一个迭代器，vector v，v数组的首元素就是 v.begin()
2. T&val , 就是一个T类型的变量
3. Compare 就是一个比较器，可以传仿函数对象，也可以传函数指针

 函数作用：

• 前提是有序的情况下，lower_bound 返回指向第一个值不小于 val 的位置，也就是返回第一个大于等于val值的位置。（通过二分查找） 

  参数、返回值含义 :

  1. first,last: 迭代器在排序序列的起始位置和终止位置，使用的范围是[first,last).包括first到last位置中的所有元素
  2. val: 在[first,last)下，也就是区分（找到大于等于val值的位置，返回其迭代器）
  3. comp： 主要针对于原型二，传一个函数对象，或者函数指针，按照它的方式来比较
  4. 返回值：返回一个迭代器，指向第一个大于等于val的位置

   举例说明：

   原型一 例1

  #include 
  #include 
  #include 
  using namespace std;
  int main()
  {
  	vector v = { 3,4,1,2,8 };
  	// 先排序
  	sort(v.begin(), v.end());  // 1 2 3 4 8
  	// 定义两个迭代器变量
  	vector::iterator iter1;
  	vector::iterator iter2;
  	// 在动态数组中寻找 >=3 出现的第一个数 并以迭代器的形式返回
  	iter1 = lower_bound(v.begin(), v.end(), 3);  // -- 指向3
  	// 在动态数组中寻找 >=7 出现的第一个数 并以迭代器的形式返回
  	iter2 = lower_bound(v.begin(), v.end(), 7);  // -- 指向8
  	cout