C++ upper_bound, lower_bound 개념정리

● lower_bound

용도 : 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함.

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

using namespace std;

int main(void){
  vector<int> v = {1,2,3,4,5,6,7,8};
  cout << "lower_bound(6) : " << lower_bound(v.begin(), v.end(), 6) - v.begin();

  return 0;
}

arr부터 끝까지 탐색하면서 6 이상의 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환하는 예제이다. lower_bound의 반환형은 Iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶으면 배열 첫 번째 주소를 가리키는 배열의 이름을 빼주면 된다. 벡터의 경우 v.begin()을 빼주면 된다.

● upper_bound

용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함

그 외에는 lower_bound와 동일