C++ STL Lower Bound 사용하기

lower_bound( begin(), end(), value)

[ begin(), end() ) 범위 중에서 value 값이 나타나는 하한을 반환한다.
만약 value가 없다면, value보다 큰 값중에서 가장 작은 값을 반환한다.

즉, value 와 같거나 큰 값이 처음 나타나는 위치를 반복자로 반환한다.

예제 1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{

    vector<int> v; // vector

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(22);

    //sort(v.begin(), v.end());

    vector<int>::iterator iter = lower_bound(v.begin(), v.end(), 22); // iterator

    cout << v[iter - v.begin()] << endl;
    cout << v[3] << endl;

    return 0;
}

위의 예제 코드의 출력 결과는 아래와 같다

30
22

sort() 함수를 이용해 정렬을 한 다음에 수행하면 아래와 같이 출력된다.

22
30

예제 2

https://www.hackerrank.com/challenges/cpp-lower-bound/problem

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */

    int m, num;
    cin >> m;
    vector<int> v;

    for (int i = 0; i < m; i++) {
      cin >> num;
      v.push_back(num);
    }

    int n, val;
    cin >> n;

    for (int i = 0; i < n; i++) {
      cin >> val;
      vector<int>::iterator low = lower_bound(v.begin(), v.end(), val);
      if (v[low - v.begin()] == val)
        cout << "Yes " << (low - v.begin() + 1) << endl;
      else
        cout << "No " << (low - v.begin() + 1) << endl;
    }

    return 0;
}