共计 644 个字符,预计需要花费 2 分钟才能阅读完成。
lower_bound&upper_bound – 二分查找函数
他们是 C ++ 自带的函数,用于在有序的数列里进行查找。留神,肯定是有序的
他们应用的是二分查找的办法,工夫复杂度为 O(logn),效率很高
应用它们要加上算法头文件,当然,能够应用万能头文件也能够
#include<algorithm> // 算法头文件
#include<bits/stdc++.h> // 万能头文件
先理解一下它们的区别
lower_bound – 数列递增序时查找大于等于查找数的第一个数,递加则查找小于等于查找数的第一个数
upper_bound – 数列递增序时查找严格大于查找数的第一个数,递加则严格小于等于查找数的第一个数
再看下应用格局
能够看出两者应用格局基本相同
lower_bound(begin, end, num);
upper_bound(begin, end, num);
然而它们的返回值是指针或迭代器,咱们要想获取下标还要再减去首地址,晓得了下标也就能够取得具体指了
举几个例子便于了解
数组内应用:
int a[5] = {1, 2, 3, 4, 5};
int p = lower_bound(a, a+5, 3)-a; //p=2
int num = a[p]; //num=3
vector 内应用
vector<int> v;
for(int i=1; i<=5; i++)
v.push_back(i);
int p = lower_bound(v.begin(), v.end(), 3)-v.begin(); //p=2
int num = v[p]; //num=3
如有疑难欢送在下方评论区提出
正文完