关于lower_bound( )和upper_bound( )的常见用法与区别

快来打我* 2023-01-23 10:51 15阅读 0赞

# lower\_bound #

*  Return iterator to lower bound
 *  Returns an iterator pointing to the first element in the range `[first,last)` which does not compare less than val.
 *  The elements are compared using `operator<` for the first version, and comp for the second. The elements in the range shall already be [sorted][] according to this same criterion (`operator<` or comp), or at least [partitioned][] with respect to val.
 *  The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for [random-access iterators][].
 *  Unlike [upper\_bound][upper_bound], the value pointed by the iterator returned by this function may also be equivalent to val, and not only greater.

# upper\_bound #

*  Return iterator to upper bound
 *  Returns an iterator pointing to the first element in the range `[first,last)` which compares greater than val.
 *  The elements are compared using `operator<` for the first version, and comp for the second. The elements in the range shall already be [sorted][] according to this same criterion (`operator<` or comp), or at least [partitioned][] with respect to val.
 *  The function optimizes the number of comparisons performed by comparing non-consecutive elements of the sorted range, which is specially efficient for [random-access iterators][].
 *  Unlike [lower\_bound][lower_bound], the value pointed by the iterator returned by this function cannot be equivalent to val, only greater.

# 总述 #

lower\_bound( )和upper\_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

# 在从小到大的排序数组中 #

lower\_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper\_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

# 在从大到小的排序数组中 #

在从大到小的排序数组中，重载lower\_bound()和upper\_bound()

lower\_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper\_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

# 代码1： #

#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;	
    }

输出

pos1=3     num[pos1]=7
    pos1=4     num[pos2]=15
    pos3=2     num[pos3]=7
    pos4=3     num[pos4]=4

# 代码2： #

// lower_bound/upper_bound example
    #include <iostream> // std::cout
    #include <algorithm> // std::lower_bound, std::upper_bound, std::sort
    #include <vector> // std::vector
    
    int main () { 
      int myints[] = { 10,20,30,30,20,10,10,20};
      std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
    
      std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30
    
      std::vector<int>::iterator low,up;
      low=std::lower_bound (v.begin(), v.end(), 20); // ^
      up= std::upper_bound (v.begin(), v.end(), 20); // ^
    
      std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
      std::cout << "upper_bound at position " << (up - v.begin()) << '\n';
    
      return 0;
    }

输出

lower_bound at position 3
    upper_bound at position 6

如图

<table> 
 <thead> 
  <tr> 
   <th align="center">数组下标</th> 
   <th align="center">0</th> 
   <th align="center">1</th> 
   <th align="center">2</th> 
   <th align="center">3</th> 
   <th align="center">4</th> 
   <th align="center">5</th> 
   <th align="center">6</th> 
   <th align="center">7</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">数组</td> 
   <td align="center">10</td> 
   <td align="center">10</td> 
   <td align="center">10</td> 
   <td align="center">20</td> 
   <td align="center">20</td> 
   <td align="center">20</td> 
   <td align="center">30</td> 
   <td align="center">30</td> 
  </tr> 
  <tr> 
   <td align="center">lower_bound</td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center">^</td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
  </tr> 
  <tr> 
   <td align="center">upper_bound</td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center"></td> 
   <td align="center">^</td> 
   <td align="center"></td> 
  </tr> 
 </tbody> 
</table>

# 练习 #

[在排序数组中查找元素的第一个和最后一个位置][Link 1]

# 参考 #

[cplusplus lower\_bound][cplusplus lower_bound]  
[关于lower\_bound( )和upper\_bound( )的常见用法][cplusplus lower_bound]

[sorted]: http://www.cplusplus.com/is_sorted
[partitioned]: http://www.cplusplus.com/is_partitioned
[random-access iterators]: http://www.cplusplus.com/RandomAccessIterator
[upper_bound]: http://www.cplusplus.com/upper_bound
[lower_bound]: http://www.cplusplus.com/lower_bound
[Link 1]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[cplusplus lower_bound]: http://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound