C++ 二分查找函数 lower_bound upper

C++ 二分查找函数 lower_bound upper_bound

阅读量：6969 次

发布时间：2019-06-27

本文共 1250 字，大约阅读时间需要 4 分钟。

lower_bound

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

　　(ForwardIterator first, ForwardIterator last,const T& val, Compare cmp)

　　返回一个 指向 [first,last) 中第一个大于等于 数val的 iterator。

upper_bound

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

　　(ForwardIterator first, ForwardIterator last,const T& val, Compare cmp)

　　返回一个 指向 [first,last) 中第一个大于 数val的 iterator。 用法示例：

#include 
     
      #include 
      
       using namespace std;int a[100];int d[100];const int INF = 0x3f3f3f3f;int main(){    int n;    int num[] = {
   1,5,2,6,8,1,2,5};    sort(num,num+sizeof(num)/sizeof(int));// 1 1 2 2 5 5 6 8    int pos1 = lower_bound(num,num+8,8) - num;//返回数组中第一个大于或等于被查数的下标位置     int pos2 = upper_bound(num,num+8,8) - num;//返回数组中第一个大于被查数的下标位置     cout << pos1 << " " << pos2 << endl;    sort(num,num+sizeof(num)/sizeof(int),greater
       
        ());//8 6 5 5 2 2 1 1    //如果从小到大排序，除非查找不到返回8，否则都返回0，没有意义。     pos1 = lower_bound(num,num+8,-1,greater
        
         ()) - num;//返回数组中第一个小于或等于被查数的下标位置     pos2 = upper_bound(num,num+8,8,greater
         
          ()) - num;//返回数组中第一个小于被查数的下标位置     cout << pos1 << " " << pos2 << endl;    return 0;}