----------------
title : C++ 레퍼런스 - std::binary_search (<algorithm>)
cat_title : binary_search
ref_title : std::binary_search, binary_search
path : /C++ Reference/algorithm
publish_date : 2020-12-07
----------------

##@ cpp-ref-start

#@ binary_search

`<algorithm>` 에 정의됨

```cpp-formatted
template <class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);  // (1)

template <class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value,
                   Compare comp);  // (2)
```

`first` 부터 `last` 전 까지의 범위 안에서 인자로 전달한 `value` 가 있는지 **이진 탐색을 통해서** 확인한다.

`std::binary_search` 는 일반적인 선형 탐색과는 다르게 이진 탐색을 사용하기 때문에 함수가 제대로 작동하기 위해서는 `[first, last)` 범위의 원소들이 최소한 `value` 를 기준으로 부분 정렬 되어 있어야만 한다. 다시 말해 아래와 같은 조건을 만족해야 한다.

* `element < value` (혹은 `comp(element, value)`) 을 기준으로 모든 원소들이 파티션 되어 있어야만 한다. 쉽게 말해 해당 식이 참인 원소들은 반드시 해당 식이 거짓인 원소들 앞에 있어야만 합니다.
* `!(value < element)` (혹은 `!comp(value, element)`) 를 기준으로 모든 원소들이 파티션 되어야만 합니다. `element < value` 와 `!(value < element)` 가 같은 것 아니냐고 물을 수 있는데 `operator<` 나 `comp` 를 어떻게 정의했냐에 따라서 아닐 수 도 있습니다.
* 모든 원소들에 대해서 `element < value` (혹은 `comp(element, value)`) 가 참이라면 `!(value < element)` (혹은 `!comp(value, element)`) 역시 참입니다.

참고로 **완전히 정렬된 원소열의 경우 위 조건을 만족합니다**

(1) 번 함수의 경우 `operator<` 를 사용해서 비교를 수행합니다.
(2) 번 함수의 경우 `comp` 함수를 이용해서 비교를 수행합니다.


밑의 두 함수의 경우 추가적으로 실행 방식을 첫 번째 인자로 전달할 수 있는데, 전달하는 `policy` 의 경우 반드시 `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` 를 만족해야 한다.

### 인자들

* `first`, `last`: 값을 탐색할 원소들의 범위를 나타낸다.
* `value` : 찾고 있는 값
* `policy` : 사용할 실행 방식
* `comp` : 두 원소를 비교할 함수로 아래와 같은 꼴 이어야 한다.

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

이 때 함수의 인자 타입은 반드시 `const&` 일 필요는 없으나, 함수안에선 반드시 전달받은 인자를 변경해서는 안된다. 또한 전달하는 인자들은 반드시 `Type1` 과 `Type2` 로 치환 가능해야만 한다.

### 리턴값

전달된 범위 내에서 원소가 존재한다면 `true` 를 리턴하고 아니면 `false` 를 리턴한다.

### 시간 복잡도

원소의 개수가 $$N$$ 이라면 최대 $$O(\log N)$$ 회의 비교를 수행하게 된다.

### 구현 예시

* [libstdc++](https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L2236)
* [libc++](https://github.com/llvm-mirror/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L4320)

```cpp-formatted
// operator< 를 사용한 버전
template <class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value) {
  first = std::lower_bound(first, last, value);
  return (!(first == last) && !(value < *first));
}
```

```cpp-formatted
// comp 함수를 사용한 버전
template <class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value,
                   Compare comp) {
  first = std::lower_bound(first, last, value, comp);
  return (!(first == last) && !(comp(value, *first)));
}
```

### 실행 예제

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

int main() {
  std::vector<int> haystack{1, 3, 4, 5, 9};
  std::vector<int> needles{1, 2, 3};

  for (auto needle : needles) {
    std::cout << "Searching for " << needle << '\n';
    if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
      std::cout << "Found " << needle << '\n';
    } else {
      std::cout << "no dice!\n";
    }
  }
}
```

```exec
Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3
```

### 참고 자료

* `equal_range` : 주어진 키와 같은 값을 가지는 원소들의 구간을 찾는다.