【C++】 详解 lower_bound 和 upper_bound 函数（看不懂来捶我！！！）

阅读本书更多章节>>>>

目录

一、前言

二、函数详解 

🥝 lower_bound

🍍upper_bound

 三、常考面试题

 四、共勉

---

一、前言

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

二、函数详解 

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

 🥝 lower_bound

 函数原型：

原型1：

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

 原型2：

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

模板参数解释：

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

 函数作用：

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

参数、返回值含义 :

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

 举例说明：

 原型一 例1

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

 注意：需要注意的是如果例子中（val >= 8）,那么迭代器就会指向last位置，也就是数组尾元素的下一个，不管val多大，迭代器永远指向尾元素的下一个位置

 原型二例2

#include <iostream>#include <algorithm>#include <vector>using namespace std;int main(){vector<int> v = { 3, 4, 1, 2, 8 };// 无序数组，不用sort排序，下面调用lower_bound排序// 定义两个迭代器变量 vector<int>::iterator iter1;vector<int>::iterator iter2;//less<int>() 是建小堆，排升序。    //greater<int>() 是建大堆，排降序//所以数组 v = {1,2,3,4,8} //我们找第一个比1大的，那肯定就是首元素1了//我们找第一个比8大的，没有，所以就指向数组最后一个元素8了iter1 = lower_bound(v.begin(), v.end(), 1, less<int>());//iter2 = lower_bound(v.begin(), v.end(), 8, less<int>());//cout << iter1 - v.begin() << endl; //下标 所以就是 0cout << iter2 - v.begin() << endl; //下标 所以就是 4system("pause");}

  注意：我们原型2的第四个参数（比较器）可以用来排序，再来获取大于等于val值的迭代器

 less<int>() 是建小堆，排升序。greater<int>() 是建大堆，排降序

 原型三 例3 仿函数传参

typedef struct Student{int _id;  //学号int _num; //排名Student(int id, int num):_id(id), _num(num){}}Stu;struct CompareV{bool operator() (const Stu& s1,  const Stu& s2)//  排名升序{return s1._num < s2._num;}};int main(){vector<Stu> vS = { { 101, 34 }, { 103, 39 }, { 102, 35 } };//CompareV()排完序后是这个丫子//101 34//102 35    //103 39auto iter = lower_bound(vS.begin(), vS.end(), Stu(200,33), CompareV());cout << iter - vS.begin() << endl; //我们就找到了按仿函数排序(找排名比33大的位置 就是0）system("pause");}

 我们了解了lower_bound的用法以后，我们再来了解一下lower_bound的原型实现 ----二分查找实现

lower_bound的底层实现 

int lower_bound(vector<int>& nums, int x) {int left = 0;int right = nums.size() - 1;    // 区间为 左闭右闭while (left <= right) {int mid = left +(right - left) / 2;if (x > nums[mid]) {left = mid + 1;}else {right = mid - 1;}}return left;}

🍍upper_bound

      用法和上面类似。只是把lower_bound的 【大于等于】 换成 【大于】 。仿函数等等全是相同的用法

底层实现 

int upper_bound(vector<int>& nums, int x) {int left = 0;int right = nums.size() - 1;while (left <= right) {int mid = left +(right - left) / 2;if (x >= nums[mid]) {       //这里是大于等于left = mid + 1;}else {right = mid - 1;}}return left;}

 三、常考面试题

题目：在排序数组中查找元素的第一个和最后一个
链接：34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {public:    vector<int> searchRange(vector<int>& nums, int target)     {         if(nums.size()==0)         {            return {-1,-1};         }         // 返回第一个 大于等于 target 的迭代器         auto index1 = lower_bound(nums.begin(),nums.end(),target);         // 返回第一个 大于 target 的迭代器         auto index2 = upper_bound(nums.begin(),nums.end(),target);         // 这个值不存在 或者 这个数不存在         if(index1==nums.end() || *index1!=target)         {            return {-1,-1};         }         // 存在         return {(int)distance(nums.begin(),index1),(int)distance(nums.begin(),index2-1)};    }};

 四、共勉

以下就是我对 lower_bound 和 upper_bound 函数 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 C++ 的更新，请持续关注我哦！！！  

 

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/xuetang/2024-04-14/158594.html，文章来源：网络cs，作者：利杜鹃，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！