Binary search and the C++ API

C++ binary search API

• template< class ForwardIt, class T, class Compare > ForwardIt std::upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ): Returns an iterator pointing to the first element in the range [first, last) that is greater than value, or last if no such element is found. Note comp is default to operator<

• template< class ForwardIt, class T, class Compare > ForwardIt std::lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp ):  Same  as upper_bound() except that it is "not less than"
• template< class ForwardIt, class T, class Compare >
  std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp ): Returns a range containing all elements equivalent to value in the range [first, last). The range [first, last) must be partitioned with respect to comparison with value, i.e. it must satisfy all of the following requirements:
  

  • partitioned with respect to element < value or comp(element, value)
  • partitioned with respect to !(value < element) or !comp(value, element)
  • for all elements, if element < value or comp(element, value) is true then !(value < element) or !comp(value, element) is also true
• set, multiset, map, multimap all have their own upper_bound() and lower_bound() method returning corresponding forward iterators.
• multimap, multiset, unordred_multimap and ordered_multiset has equal_range() method

   multiset<int> s{1,2,3,3,3,3,5,7};
    auto it = s.lower_bound(3);
    cout << (*it) << endl;
    it++; it++; it++; it++;
    cout << (*it) << endl;

    vector<int> v{1,2,3,3,3,3,5,7};
    auto vit = lower_bound(v.begin(),v.end(), 3);
    cout << (vit-v.begin()) << endl;
    cout << upper_bound(v.begin(), v.end(), 3) - v.begin() << endl;
    auto range = equal_range(v.begin(), v.end(), 3);
    cout << (range.first - v.begin()) << "," << (range.second - v.begin()) << endl;


For a sorted array in ascending order:

• Implementing upper_bound():

    int l = 0, r = v.size();
    const int target = 3;
    while (l < r) {
        auto mid = l + (r - l)/2;
        if (v[mid] > target) r = mid;
        else l = mid + 1;
    }
    cout << r << endl;

• Implementing reverse_upper_bound():

    l = -1, r = v.size()-1;
    while (l < r) {
        auto mid = r - (r - l)/2;
        if (v[mid] < target) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;

• Implementing lower_bound():

     v[reverse_upper_bound() + 1] == target ? upper_bound() : reverse_upper_bound() + 1;

• Implementing reverse_lower_bound():

     v[upper_bound() - 1] == target ? reverse_upper_bound() : upper_bound() - 1;

• Implementing equal_range():

     range.first = lower_bound(), range.second = upper_bound();