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& 일 필요는 없으나, 함수안에선 반드시 전달받은 인자를 변경해서는 안된다. 또한 전달하는 인자들은 반드시 Type1 과 Type2 로 치환 가능해야만 한다.

리턴값

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

시간 복잡도

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

구현 예시

• libstdc++

• libc++

// 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 : 주어진 키와 같은 값을 가지는 원소들의 구간을 찾는다.

첫 댓글을 달아주세요!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

다음으로 로그인

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글 달기

댓글을 불러오는 중입니다..