继续学习algorithm库中的函数，upper_bound和lower_bound是两个很有用的函数，我们先看一下关于两个函数的解释（《C++宝典》P446页中摘录）： lower_bound接受一个键值类型的参数。如果容器中某个元素的键值等于该参数，那么函数就返回指向该元素的迭代器。如果不存在这样的元素，则返回一个迭代器，指向第一个键值比参数大的元素。如果所有的元素的键值都比参数小，那么函数就返回容器的尾部，即等于end。 upper_bound正好与lower_bound相反。该函数返回的也是一个迭代器，指向第一个键值比参数大的元素，或者键值等于参数的元素。upper_bound返回的迭代器，指向键值大于参数的元素。如果所有元素的键值都比参数大，那么函数就返回容器尾部，即等于end。 备忘（高手们可跳过） 《C++宝典》中P446在篇章"关联式容器map中”，又因为插入map的时候元素自动会从小到大排序，所以没有强调这一点：容器中的元素必须是有序的！这里用来提醒自己。 关于upper_bound和lower_bound的效率： upper_bound和lower_bound都是利用了二分法解决的，其实我们可以将upper_bound和lower_bound当C语言中的bsearch使用，看我的代码： #include <iostream> #include <cstdio> #include <algorithm> using namespace std; int array[200000]; int main() { int n,ask,pos; freopen("find.in","r",stdin);
freopen("find.out","w",stdout); for(int i=0;i<n;i++) cin>>array[i]; cin>>ask; sort(array,array+n); pos=lower_bound(array,array+n,ask)-array; if(array[pos]!=ask) cout<<-1<<endl; else cout<<pos<<endl; return 0; } 这样就利用了upper_bound实现了二分查找。以上程序还自带一个小功能：可以查找到第一个出现的key。 我的随机种子生成器： #include <iostream> #include <cstdio> #include <ctime> #include <cstdlib> using namespace std; int main() { int n; freopen("find.in","w",stdout); cin>>n; cout<<n<<endl; srand((unsigned long)time(0)); for(int i=0;i<n;i++) cout<<rand()0000<<" "; cout<<endl; cout<<rand()0000<<endl; return 0; } 我们再来举一个例子，来表现upper_bound和lower_bound的好处： 题意：给你n个数字（n<=200000），再给你一个数字m，让你输出数字m在n个数字中出现的次数。 这道题完全可以使用upper_bound+lower_bound实现，我们只需要将upper_bound返回的迭代器和lower_bound返回的迭代器相减的绝对值就可以了。 见代码： #include <iostream> #include <algorithm> #include <cstdio> using namespace std; int num[1000]; int main() { int n,ask,up,down; freopen("find.in","r",stdin); freopen("find.out","w",stdout); while(cin>>n) { for(int i=0;i<n;i++) cin>>num[i]; cin>>ask; sort(num,num+n); for(int i=0;i<n;i++) cout<<num[i]<<" "; cout<<endl; up=upper_bound(num,num+n,ask)-num; //cout<<up<<endl; down=lower_bound(num,num+n,ask)-num; //cout<<down<<endl; cout<<up-down<<endl; } return 0; }
分享：