函数的头文件： #include <algorithm>
lower_bound
lower_bound( begin,end,num)
从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，
不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
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");
}
例:仿函数传参
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的底层实现
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的 【大于等于】 换成【大于】。
仿函数等等全是相同的用法
upper_bound(begin,end,num)
从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，
不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
示例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自定义比较函数
找到第一个大于 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;
}
找到第一个能被 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[HTML_REMOVED]() 自定义比较函数：适用于从小到大排序的有序序列，从数组/容器的 beign 位置起，到 end-1 位置结束，查找第一个 大于 val 的数字
upper_bound( begin , end , val , greater<type>() )
上述代码中加入了 greater[HTML_REMOVED]() 自定义比较函数：适用于从大到小排序的有序序列，从数组/容器的 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;
}
例题AcWing 789. 数的范围
在排序数组中查找元素的第一个和最后一个
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
void solve(int k, vector<int> &v)
{
int l = lower_bound(v.begin(), v.end(), k) - v.begin();
int r = upper_bound(v.begin(), v.end(), k) - v.begin();
if(v[l] == k) cout<<l<<' ';
else cout<<-1<<' ';
if(v[r - 1] == k) cout<<r-1<<endl;
else cout<<-1<<endl;
}
int main()
{
int n, q, k, tmp;
cin>>n>>q;
vector<int> v;
for(int i = 0; i < n; i ++)
{
cin >> tmp; v.push_back(tmp);
}
while(q --)
{
cin >> k;
solve(k, v);
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
const int INF=2*int(1e9)+10;
#define LL long long
int cmd(int a,int b){
return a>b;
}
int main(){
int num[6] = {1,2,4,7,15,34};
sort(num,num + 6); //按从小到大排序
int pos1 = lower_bound(num,num + 6,7) - num; //返回数组中第一个大于或等于被查数的值
int pos2 = upper_bound(num,num + 6,7) - num; //返回数组中第一个大于被查数的值
cout<<pos1<<" "<<num[pos1]<<endl;
cout<<pos2<<" "<<num[pos2]<<endl;
sort(num,num + 6,cmd); //按从大到小排序
int pos3 = lower_bound(num,num + 6,7,greater<int>()) - num; //返回数组中第一个小于或等于被查数的值
int pos4 = upper_bound(num,num + 6,7,greater<int>()) - num; //返回数组中第一个小于被查数的值
cout<<pos3<<" "<<num[pos3]<<endl;
cout<<pos4<<" "<<num[pos4]<<endl;
return 0;
}
