경계값 iterator 찾기 lower_bound() 와 upper_bound()

https://www.acmicpc.net/problem/18870

이 문제가 대표적인 예다.

 

** find로 경계값 찾는 것 보다 이게 더 빠르다.

find는 O(N) 시간 복잡도를 가지기 때문이다.

 

lower_bound는 이진탐색 기반이라 빠르다고 한다.

**그래서 set 기본 메서드에도 lower_bound가 존재한다.

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - set으로 중복없애고 자동 정렬하기

 

 

 

lower_bound(first, last, value)는 value보다 작은 값의 경계를 반환한다.

upper_bound(first, last, value)는 value보다 큰 값의 경계를 반환한다.

 

// lower_bound/upper_bound example
#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

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

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

  std::vector<int>::iterator low,up;
  low=std::lower_bound (v.begin(), v.end(), 20); //          ^
  up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

  std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
  std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

  return 0;
}

 

쉽게 말하면 

lower_bound는 리턴한 iterator가 바로 value 이상이 되는 지점이다.

upper_bound는 리턴한 iterator가 바로 value를 초과하는 지점이다.

 

https://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound