目录

一、前言

二、函数详解 

 🥝 lower_bound

⚡无自定义比较函数

⚡使用自定义比较函数

 ✨ 自己写--自定义比较函数

 ✨ 官方的--自定义比较函数

🍍upper_bound

⚡无自定义比较函数

⚡使用自定义比较函数 

 ✨ 自己写--自定义比较函数

 ✨ 官方的--自定义比较函数

🍇 upper_bound 和 lower_bound 的区别

 三、常考面试题

 四、共勉

一、前言

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

二、函数详解 

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

函数的头文件： #include <algorithm>

 🥝 lower_bound

 函数原型：

原型1：

<code>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

template <class ForwardIterator, class T>

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

#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); // -- 指向8

cout << distance(v.begin(), iter1) << endl; //下标 2

cout << distance(v.begin(), iter2) << endl; //下标 4

return 0;

}

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

⚡使用自定义比较函数

原型二例2

template <class ForwardIterator, class T, class Compare>

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

 ✨ 自己写--自定义比较函数

 返回 第一个 false 的元素     val 是自定义函数中的 第二个参数

可能大家不太能理解这句话，这里给大家举两个例子 

例子1： 找到 第 1 个小于 20 的元素

// 自定义函数

// 目的是 找出 大于等于 val 的元素

bool cmp(const int& e, const int& val)

{

return e >= val;

}

int main()

{

// 有序数组---从大到小

vector<int> v = { 30,28,26,25,21,20,19,16,1 };

// lower_bound 的目的：找出第一个 false 自定义函数的值---即 第 1 个 < 20 的元素

vector<int>::iterator it = lower_bound(v.begin(), v.end(), 20, cmp);

if (it == v.end())

cout << "未找到满足条件的元素" << endl;

else

{

cout << *it << endl; // 找到的元素为：19

cout << it - v.begin() << endl; // 下标为：6

}

return 0;

}

例子2： 找到第 1 个 无法 被 5 整除 的元素

// 自定义函数

// 目的是 找出 能够整除 val 的元素

bool cmp(const int& e, const int& val)

{

return (e % val) == 0;

}

int main()

{

// 有序数组---从大到小

vector<int> v = { 30,28,26,25,21,20,19,16,1 };

// lower_bound 的目的：找出第一个 false 自定义函数的值---即 第 1 个 无法被 val整除 的元素

vector<int>::iterator it = lower_bound(v.begin(), v.end(), 5, cmp);

if (it == v.end())

cout << "未找到满足条件的元素" << endl;

else

{

cout << *it << endl; // 找到的元素为：28

cout << it - v.begin() << endl; // 下标为：1

}

return 0;

}

 ✨ 官方的--自定义比较函数

lower_bound( begin , end , val , less<type>() )

上述代码中加入了 less<type>() 自定义比较函数：适用于从小到大排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找第一个 大于等于 val 的数字

lower_bound( begin , end , val , greater<type>() )

上述代码中加入了 greater<type>() 自定义比较函数：适用于从大到小排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找第一个 小于等于 val 的数字

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main()

{

vector<int> v = { 3, 4, 1, 2, 8 }; // 无序数组

// 定义两个迭代器变量

vector<int>::iterator iter1;

vector<int>::iterator iter2;

// 排序默认为 ： 从小到大

sort(v.begin(), v.end());

//此时数组为 v = {1,2,3,4,8}

//找 第一个大于 等于 val 的数字

iter1 = lower_bound(v.begin(), v.end(), 2, less<int>());

iter2 = lower_bound(v.begin(), v.end(), 9, less<int>());

cout << iter1 - v.begin() << endl; //下标 所以就是 1

cout << iter2 - v.begin() << endl; //下标 所以就是 5

// 排序：从大到小

sort(v.begin(), v.end(), greater<int>());

//此时数组为 v = {8，4，3，2，1}

// 找 第一个小于 等于 val 的数字

iter1 = lower_bound(v.begin(), v.end(), 2, greater<int>());

iter2 = lower_bound(v.begin(), v.end(), 9, greater<int>());

cout << iter1 - v.begin() << endl; //下标 所以就是 3

cout << iter2 - v.begin() << endl; //下标 所以就是 0

system("pause");

}

 原型三 例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 39

auto 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

 函数作用：

 前提是有序的情况下，upper_bound 返回第一个大于--val值的位置。（通过二分查找） 用法和上面类似。只是把lower_bound的 【大于等于】 换成 【大于】 。仿函数等等全是相同的用法 

 举例说明：

 ⚡无自定义比较函数

 原型一 例1

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 = upper_bound(v.begin(), v.end(), 3); // -- 指向4

// 在动态数组中寻找 >7 出现的第一个数 并以迭代器的形式返回

iter2 = upper_bound(v.begin(), v.end(), 7); // -- 指向8

cout << distance(v.begin(), iter1) << endl; //下标 3

cout << distance(v.begin(), iter2) << endl; //下标 4

return 0;

}

⚡使用自定义比较函数 

 原型二 例2

 ✨ 自己写--自定义比较函数

  返回 第一个 true 的元素     val 是自定义函数中的 第一个参数

  返回第一个 满足 cmp (返回true) 的 元素 的迭代器

 可能大家不太能理解这句话，这里给大家举两个例子 

 例子1：找到第一个大于 5 的元素，返回其迭代器

// 自定义函数

// 目的是 找出 大于 val 的元素

bool cmp2(const int& val, const int& e)

{

return val < e;

}

int main()

{

// 有序数组---从大到小

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

// upper_bound 的目的：找出第一个 true 自定义函数的值---即 第 1 个 大于 val 的元素

vector<int>::iterator it = upper_bound(v.begin(), v.end(), 5, cmp2);

if (it == v.end())

cout << "未找到满足条件的元素" << endl;

else

{

cout << *it << endl; // 找到的元素为：6

cout << it - v.begin() << endl; // 下标为：4

}

return 0;

}

例子2： 找到第一个能被 5 整除 的元素

// 自定义函数

// 目的是 找出 大于 val 的元素

bool cmp2(const int& val, const int& e)

{

return (e % val) == 0;

}

int main()

{

// 有序数组---从大到小

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

// upper_bound 的目的：找出第一个 true 自定义函数的值---即 第 1 个 能够被val整除 的元素

vector<int>::iterator it = upper_bound(v.begin(), v.end(), 5, cmp2);

if (it == v.end())

cout << "未找到满足条件的元素" << endl;

else

{

cout << *it << endl; // 找到的元素为：5

cout << it - v.begin() << endl; // 下标为：3

}

return 0;

}

 ✨ 官方的--自定义比较函数

upper_bound( begin , end , val , less<type>() )

上述代码中加入了 less<type>() 自定义比较函数：适用于从小到大排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找第一个 大于 val 的数字

upper_bound( begin , end , val , greater<type>() )

上述代码中加入了 greater<type>() 自定义比较函数：适用于从大到小排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找第一个 小于 val 的数字

int main()

{

vector<int> v = { 3, 4, 1, 2, 8 }; // 无序数组

// 定义两个迭代器变量

vector<int>::iterator iter1;

vector<int>::iterator iter2;

// 排序默认为 ： 从小到大

sort(v.begin(), v.end());

//此时数组为 v = {1,2,3,4,8}

//找 第一个大于 val 的数字

iter1 = upper_bound(v.begin(), v.end(), 2, less<int>());

iter2 = upper_bound(v.begin(), v.end(), 9, less<int>());

cout << iter1 - v.begin() << endl; //下标 所以就是 2

cout << iter2 - v.begin() << endl; //下标 所以就是 5

// 排序：从大到小

sort(v.begin(), v.end(), greater<int>());

//此时数组为 v = {8，4，3，2，1}

// 找 第一个小于 val 的数字

iter1 = upper_bound(v.begin(), v.end(), 2, greater<int>());

iter2 = upper_bound(v.begin(), v.end(), 9, greater<int>());

cout << iter1 - v.begin() << endl; //下标 所以就是 4

cout << iter2 - v.begin() << endl; //下标 所以就是 0

system("pause");

}

底层实现 

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;

}

🍇 upper_bound 和 lower_bound 的区别

auto it1 = lower_bound(v.begin(), v.end(), val,cmp1);

auto it2 = upper_bound(v.begin(), v.end(), val,cmp2);

 三、常考面试题

题目：在排序数组中查找元素的第一个和最后一个

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

<code>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++ 的更新，请持续关注我哦！！！