Hàm lower_bound trong thư viện algorithm (DevC++)

function template:

template <class ForwardIterator, class T>
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value );

template <class ForwardIterator, class T, class Compare>
  ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value, Compare comp );

Hàm lower_bound trả về vị trí đầu tiên của phần tử cần tìm trong nửa khoảng [first,last).
Comparision được sử dụng trong phiên bản 1 là operator<, còn trong phiên bản 2 là đối tượng comp.


Tương tự chúng ta có hàm upper_bound:
function template:
template <class ForwardIterator, class T>
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value );

template <class ForwardIterator, class T, class Compare>
  ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,
                                const T& value, Compare comp );


Ví dụ:

// lower_bound/upper_bound example
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
  int myints[] = {10,20,30,30,20,10,10,20};
  vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20
  vector<int>::iterator low,up;

  sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

  low=lower_bound (v.begin(), v.end(), 20); //          ^
  up= upper_bound (v.begin(), v.end(), 20); //                   ^

  cout << "lower_bound at position " << int(low- v.begin()) << endl;
  cout << "upper_bound at position " << int(up - v.begin()) << endl;

  return 0;
}

Tham khảo: http://www.cplusplus.com/reference/algorithm/lower_bound/