[C++][STL] binary_search

比眉伴天荒 2022-04-11 05:28 125阅读 0赞

所需的页眉
       <algorithm>
    
    回到顶端
    原型
       template<class ForwardIterator, class T> inline
           ForwardIterator upper_bound(ForwardIterator first,
                                       ForwardIterator last,
                                       const T& value)
    
    注： 在原型中的类/参数名称与在头文件中的与原始版本不匹配。他们已被修改，以提高可读性。
    回到顶端
    说明
    upper_bound 算法将最后一个位置返回序列中的序列的顺序进行维护，可以在插入值。 
    
    upper_bound 返回迭代器放在该位置的值可将插入在范围 [第一次...最后一次），或如果没有此类位置存在，则返回上一次。 
    
    upper_bound 假定范围 [第一次...最后一次） 进行排序使用运算符 <。
    回到顶端
    示例代码
    // 
    // 
    // Compile options needed: /GX
    // 
    // upper_bound.cpp : Illustrates how to use the upper_bound
    //                   function.
    // 
    // Functions:
    // 
    //    upper_bound : Return the upper bound within a range.
    // 
    // Written by Kalindi Sanghrajka
    // of Microsoft Product Support Services,
    // Software Core Developer Support.
    // Copyright (c) 1996 Microsoft Corporation. All rights reserved.
    // 
    
    // disable warning C4786: symbol greater than 255 character,
    // okay to ignore
    #pragma warning(disable: 4786)
    
    #include <iostream>
    #include <algorithm>
    #include <functional>
    #include <vector>
    using namespace std;
    
    void main()
    {
       
        const int VECTOR_SIZE = 8 ;
    
        // Define a template class vector of int
        typedef vector<int, allocator<int> > IntVector ;
    
        //Define an iterator for template class vector of strings
        typedef IntVector::iterator IntVectorIt ;
    
        IntVector Numbers(VECTOR_SIZE) ;
    
        IntVectorIt start, end, it, location ;
    
        // Initialize vector Numbers
        Numbers[0] = 4 ;
        Numbers[1] = 10;
        Numbers[2] = 10 ;
        Numbers[3] = 30 ;
        Numbers[4] = 69 ;
        Numbers[5] = 70 ;
        Numbers[6] = 96 ;
        Numbers[7] = 100;
    
        start = Numbers.begin() ;   // location of first
                                    // element of Numbers
    
        end = Numbers.end() ;       // one past the location
                                    // last element of Numbers
    
        // print content of Numbers
        cout << "Numbers { " ;
        for(it = start; it != end; it++)
            cout << *it << " " ;
        cout << " }\n" << endl ;
    
        //return the last location at which 10 can be inserted
        // in Numbers
        location = upper_bound(start, end, 10) ;
    
        cout << "Element 10 can be inserted at index "
            << location - start << endl ;
    }
    
    程序输出为：
    Numbers { 4 10 10 30 69 70 96 100  }

Lower_bound 和 upper_bound的区别
    
    lower_bound: the position that found is the first pos which value is not lower than compare value
    upper_bound: the position that found is the first pos which value is larger than compare value
    例子：
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    
    int main()
    {
       
      int A[] = { 1, 2, 3, 3, 3, 5, 8 };
      const int N = sizeof(A) / sizeof(int);
    
      for (int i = 1; i <= 10; ++i) {
       
        int * p = upper_bound(A, A + N, i);
        int * q = lower_bound(A,A+N,i);
        cout << "Searching for " << i << ".  "<<endl;
        cout << "upper_bound Result: index = " << p - A << ", "<<endl;
        cout << "lower_bound Result: index = " << q - A << ", "<<endl;
        if (p != A + N)
        {
       
          cout << "upper_bound A[" << p - A << "] == " << *p << endl;
          cout << "lower_bound A[" << q - A << "] == " << *q << endl;
        }
        else
          cout << "which is off-the-end." << endl;
        cout<<"--------------------------------"<<endl;
      }
      return 0;
    }

if (keyScopeItem.getEnableAggregation())
        {
       
            bool isMatch = false;
            ScopeStartEndValuesMap::const_iterator upperIter = keyScopeItem.getKeyScopeValues().upper_bound(keyScopeItem.getAggregateKeyValue());
            if ( upperIter != keyScopeItem.getKeyScopeValues().begin() )
            {
       
                --upperIter;
    
                if ( keyScopeItem.getAggregateKeyValue() >= upperIter->first 
                && keyScopeItem.getAggregateKeyValue() <=  upperIter->second )
                {
       
                    isMatch = true;
                }
            }
    
            // will match...
            if ( isMatch )
            {
       
                eastl::string msg;
                msg.sprintf("[StatsConfigData].parseKeyScopeItem(): key scope item [%s] has non-unique aggregate key value [%"PRId64"]",
                    keyScopeItemName, keyScopeItem.getAggregateKeyValue());
                TdfString& str = validationErrors.getErrorMessages().push_back();
                str.set(msg.c_str());
                return false;
            }
        }