----------------
title : C++ 레퍼런스 - std::lower_bound 와 upper_bound (<algorithm>)
cat_title : lower_bound, upper_bound
ref_title : lower_bound, upper_bound, std::lower_bound, std::upper_bound
path : /C++ Reference/algorithm
publish_date : 2019-09-20
----------------

##@ cpp-ref-start

#@ lower_bound, upper_bound

`<algorithm>` 에 정의됨

```cpp-formatted
// 참고로 C++ 20 부터 모두 constexpr 함수 이다.
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value);
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value);

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

#### lower_bound

범위 `[first, last)` 안의 원소들 중, `value` 보다 **작지 않은 (크거나 같은)** 첫 번째 원소를 리턴한다. 만일 그런 원소가 없다면 `last` 를 리턴한다. 이름 그대로 **어떠한 값의 하한선** 을 의미한다.

#### upper_bound

범위 `[first, last)` 안의 원소들 중, `value` 보다 **큰** 첫 번째 원소를 리턴한다. 만일 그런 원소가 없다면 `last` 를 리턴한다. 이름 그대로 **어떠한 값의 상한선** 을 의미한다.

**이 때 위 두 함수가 작동하기 위해서는 범위안에 있는 원소들이 정렬된 상태여야 한다.** 엄밀히 말하자면, `lower_bound` 함수의 경우 `element < value` 를 만족하는 모든 `element` 들은 해당 식을 만족하지 않는 원소들 보다 앞에 있어야 한다. 마찬가지로 `upper_bound` 의 경우 !(value < element) 를 만족하는 모든 `element` 들은 해당 식을 만족하지 않는 원소들 보다 앞에 있어야 한다. 물론, 범위 안에 있는 원소들이 정렬된 상태라면 해당 조건을 만족한다.

첫 번째 함수 버전은 `operator<` 를 사용해서 비교를 수행하고, 두 번째 버전은 `Comp` 함수를 사용해서 비교를 수행한다.

### 인자들

* `first, last` : 원소들의 범위를 나타내는 반복자. (각각 첫 번째 원소와 마지막 원소 바로 다음을 가리킴) 이 때 해당 원소들은 위의 조건에 맞게 정렬되어 있어야 한다.
* `value`	: 원소들의 값을 비교할 값
* `comp` : 비교를 수행하는 이항 함수. 아래와 같은 꼴이어야 한다.

```cpp-formatted
bool pred(const Type1 &a, const Type2 &b);
```

참고로 인자가 `const&` 일 필요는 없지만, 전달 받은 원소를 함수 내부에서 수정하면 안된다. 또한 `Type1` 과 `Type2` 는 반복자가 가리키고 있는 타입과 같거나 변환될 수 있어야 한다. 물론 알고리즘 내부적으로 `pred` 함수에 `const` 원소를 전달할 수 있으므로, `Type1` 과 `Type2` 가 `const&` 인 것이 좋다. (컴파일 오류가 발생할 수 도 있음)

참고로 `ForwardIt` 은 반드시 `LegacyForwardIterator` 를 만족해야 하며, `Compare` 은 반드시  `BinaryPredicate` 조건을 만족해야 한다.

### 리턴값

위 조건을 만족하는 반복자를 리턴한다. 이 때 해당 조건을 만족하는 반복자가 없을 시에 `last` 를 리턴한다.

### 시간 복잡도

전체 원소 개수에 로그에 비례한다. 즉 $$O(\log(\text{last} - \text{first}))$$ 이다.

### 구현 예시

#### lower_bound

```cpp-formatted
template <class ForwardIt, class T>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value) {
  ForwardIt it;
  typename std::iterator_traits<ForwardIt>::difference_type count, step;
  count = std::distance(first, last);

  while (count > 0) {
    it = first;
    step = count / 2;
    std::advance(it, step);
    if (*it < value) {
      first = ++it;
      count -= step + 1;
    } else
      count = step;
  }
  return first;
}
```

#### upper_bound

```cpp-formatted
template <class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value) {
  ForwardIt it;
  typename std::iterator_traits<ForwardIt>::difference_type count, step;
  count = std::distance(first, last);

  while (count > 0) {
    it = first;
    step = count / 2;
    std::advance(it, step);
    if (!(value < *it)) {
      first = ++it;
      count -= step + 1;
    } else
      count = step;
  }
  return first;
}
```

#### 실행 예제

```cpp-formatted
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
  std::vector<int> data = {1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};

  auto lower = std::lower_bound(data.begin(), data.end(), 4);
  auto upper = std::upper_bound(data.begin(), data.end(), 4);

  std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
  return 0;
}
```

```exec
4 4 4 
```

### 참고 자료

* `equal_range` : 해당 `key` 와 같이 같은 원소들의 범위를 리턴한다.
* `partition` : 두 그룹의 원소들로 파티션 한다.