모두의 코드
C++ 레퍼런스 - std::binary_search (<algorithm>)

작성일 : 2020-12-07 이 글은 871 번 읽혔습니다.

아직 C++ 에 친숙하지 않다면 씹어먹는 C++ 은 어때요?

binary_search

<algorithm> 에 정의됨

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 : 두 원소를 비교할 함수로 아래와 같은 꼴 이어야 한다.

bool cmp(const Type1 &a, const Type2 &b);

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

리턴값

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

시간 복잡도

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

구현 예시

// 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));
}
// 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)));
}

실행 예제

#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";
    }
  }
}

실행 결과

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

참고 자료

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

첫 댓글을 달아주세요!
프로필 사진 없음
강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요