STL中的二分查找——lower_bound 、upper_bound 、binary_search

蔚落 2022-03-19 08:38 150阅读 0赞

二分查找很简单，原理就不说了。STL中关于二分查找的函数有三个lower\_bound 、upper\_bound 、binary\_search 。这三个函数都运用于有序区间（当然这也是运用二分查找的前提）。

其中如果寻找的value存在，那么lower\_bound返回一个迭代器指向其中第一个这个元素。upper\_bound返回一个迭代器指向其中最后一个这个元素的下一个位置（明确点说就是返回在不破坏顺序的情况下，可插入value的最后一个位置）。如果寻找的value不存在，那么lower\_bound和upper\_bound都返回“假设这样的元素存在时应该出现的位置”。要指出的是lower\_bound和upper\_bound在源码中只是变换了if—else语句判定条件的顺序，就产生了最终迭代器位置不同的效果。

binary\_search试图在已排序的\[first,last)中寻找元素value，若存在就返回true，若不存在则返回false。返回单纯的布尔值也许不能满足需求，而lower\_bound、upper\_bound能提供额外的信息。事实上由源码可知binary\_search便是利用lower\_bound求出元素应该出现的位置，然后再比较该位置   的值与value的值。该函数有两个版本一个是operator< ，另外一个是利用仿函数comp进行比较。

具体分析见源码

//这是forward版本
    template <class ForwardIterator, class T>
    inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                       const T& value) {
      return __lower_bound(first, last, value, distance_type(first),
                           iterator_category(first));
    }
    
    // 这是版本一的 forward_iterator 版本
    template <class ForwardIterator, class T, class Distance>
    ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
                                  const T& value, Distance*,
                                  forward_iterator_tag) {
      Distance len = 0;
      distance(first, last, len);	// 求取整个范围的长度，ForwardIterator没有-n操作
      Distance half;
      ForwardIterator middle;
    
      while (len > 0) {                        //为了跳出循环，而定义了len，如果用while(true) 然后每次判定长度在break，也行，不过没这个好
        half = len >> 1;			// 除以2，注意这种移位写法，不需编译器进行优化
        middle = first;			     // 这两行令middle 指向中间位置
        advance(middle, half);       //ForwardIterator没有+n的操作
        if (*middle < value) {		// 如果中间位置的元素值 < 标的值，value在后半区间
          first = middle;			// 这两行令 first 指向 middle 的下一位置
          ++first;
          len = len - half - 1;		// 修正 len，回头测试循环条件
        }
    else						// 注意如果是相等的话，那么执行的是else语句，在前半部分找
    							// 与opper_bound进行比较
          len = half;				// 修正 len，回头测试循环条件
      }
      return first;
    }
    // 这是带comp反函数的 forward_iterator 版本
    template <class ForwardIterator, class T, class Compare, class Distance>
    ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,
                                  const T& value, Compare comp, Distance*,
                                  forward_iterator_tag) {
      Distance len = 0;
      distance(first, last, len);
      Distance half;
      ForwardIterator middle;
    
      while (len > 0) {
        half = len >> 1;
        middle = first;
        advance(middle, half);
        if (comp(*middle, value)) {
          first = middle;
          ++first;
          len = len - half - 1;
        }
        else
          len = half;
      }
      return first;
    }
    
    // 这是random_access_iterator版本
    template <class ForwardIterator, class T, class Compare>
    inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
                                       const T& value, Compare comp) {
      return __lower_bound(first, last, value, comp, distance_type(first),
                           iterator_category(first));
    }
    
    // 这是版本一的 random_access_iterator 版本
    template <class RandomAccessIterator, class T, class Distance>
    RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                       RandomAccessIterator last, const T& value,
                                       Distance*, random_access_iterator_tag) {
      Distance len = last - first;	//求取整个范围的长度，与ForwarIterator版本进行比较
      Distance half;
      RandomAccessIterator middle;
    
      while (len > 0) {
    half = len >> 1;			
    middle = first + half;		
        if (*middle < value) {		
          first = middle + 1;		
          len = len - half - 1;		//修正 len，回头测试循环条件，RamdonAccessIterator版本
        }
        else
          len = half;				
      }
      return first;
    }
    
    
    
    //这是带comp仿函数 random_access_iterator 版本
    template <class RandomAccessIterator, class T, class Compare, class Distance>
    RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                       RandomAccessIterator last,
                                       const T& value, Compare comp, Distance*,
                                       random_access_iterator_tag) {
      Distance len = last - first;
      Distance half;
      RandomAccessIterator middle;
    
      while (len > 0) {
        half = len >> 1;
        middle = first + half;
        if (comp(*middle, value)) {
          first = middle + 1;
          len = len - half - 1;
        }
        else
          len = half;
      }
      return first;
    }
    
    // 这是forward_iterator版本
    template <class ForwardIterator, class T>
    inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                       const T& value) {
      return __upper_bound(first, last, value, distance_type(first),
                           iterator_category(first));
    }
    
    // 这是版本一的 forward_iterator 版本
    template <class ForwardIterator, class T, class Distance>
    ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
                                  const T& value, Distance*,
                                  forward_iterator_tag) {
      Distance len = 0;
      distance(first, last, len);	
      Distance half;
      ForwardIterator middle;
    
      while (len > 0) {
        half = len >> 1;			
        middle = first;			    
        advance(middle, half);
        if (value < *middle)		// 如果中间位置的元素值大于标的值，证明在前半部分
          len = half;				// 修正len
    else {						// 注意如果元素值相等的话，那么是在后半部分找
    							// 与lower_bound进行比较
          first = middle;			// 在下半部分，令first指向middle的下一个位置
          ++first;
          len = len - half - 1;		// 修正 len
        }
      }
      return first;
    }
    
    // 这是版本一的 random_access_iterator 版本
    template <class RandomAccessIterator, class T, class Distance>
    RandomAccessIterator __upper_bound(RandomAccessIterator first,
                                       RandomAccessIterator last, const T& value,
                                       Distance*, random_access_iterator_tag) {
      Distance len = last - first;	
      Distance half;
      RandomAccessIterator middle;
    
      while (len > 0) {
        half = len >> 1;			
        middle = first + half;		
        if (value < *middle)		
          len = half;				    
    	 else {
          first = middle + 1;		
          len = len - half - 1;		
        }
      }
      return first;
    }
    
    // 这是带comp的版本
    template <class ForwardIterator, class T, class Compare>
    inline ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
                                       const T& value, Compare comp) {
      return __upper_bound(first, last, value, comp, distance_type(first),
                           iterator_category(first));
    }
    
    // 这是带comp的 forward_iterator 版本
    template <class ForwardIterator, class T, class Compare, class Distance>
    ForwardIterator __upper_bound(ForwardIterator first, ForwardIterator last,
                                  const T& value, Compare comp, Distance*,
                                  forward_iterator_tag) {
      Distance len = 0;
      distance(first, last, len);
      Distance half;
      ForwardIterator middle;
    
      while (len > 0) {
        half = len >> 1;
        middle = first;
        advance(middle, half);
        if (comp(value, *middle))
          len = half;
        else {
          first = middle;
          ++first;
          len = len - half - 1;
        }
      }
      return first;
    }
    
    // 这是带comp的 random_access_iterator 版本
    template <class RandomAccessIterator, class T, class Compare, class Distance>
    RandomAccessIterator __upper_bound(RandomAccessIterator first,
                                       RandomAccessIterator last,
                                       const T& value, Compare comp, Distance*,
                                       random_access_iterator_tag) {
      Distance len = last - first;
      Distance half;
      RandomAccessIterator middle;
    
      while (len > 0) {
        half = len >> 1;
        middle = first + half;
        if (comp(value, *middle))
          len = half;
        else {
          first = middle + 1;
          len = len - half - 1;
        }
      }
      return first;
    }
    
    // 版本一
    template <class ForwardIterator, class T>
    bool binary_search(ForwardIterator first, ForwardIterator last,
                       const T& value) {
      ForwardIterator i = lower_bound(first, last, value);  
    //这里的实现就是调用的lower_bound ，并且如果元素不存在那么lower_bound指向的元素一定是
    //operator < 为ture的地方。
      return i != last && !(value < *i);
    }
    
    // 版本二
    template <class ForwardIterator, class T, class Compare>
    bool binary_search(ForwardIterator first, ForwardIterator last, const T& value,
                       Compare comp) {
      ForwardIterator i = lower_bound(first, last, value, comp);
      return i != last && !comp(value, *i);
    }