Binary Search

작성일 | In

가장 기본적이고, 쉬운 탐색방법이 이분탐색이다. 학교에서는 단순하게만 배우는데, 알고리즘 문제 해결용으로 좀 더 실질적인 사용법들을 다뤄보고자 한다.

이 글은 top-coder의 Binary Search 칼럼에서 읽은 내용을 다시 풀어쓴 글이다. 이 포스팅이 내용이 부족하다고 생각될 경우에는 원문을 참고하길 바란다.

학교에서 배운 방식

학교에서 쉽게 배우는 방식은 아래와 같다. 기본적으로 배열 arr는 정렬되어 있어야 한다.

1
2
3
4
5
6
7
8
9
10
int bs(int v) {
  int lo = 0, hi = size_of_array-1;
  while (lo < hi) {
    int m = (lo+hi)/2;
    if(arr[m] == v) return m;
    else if (arr[m] < v) lo = m + 1;
    else hi = m - 1;
  }
  return -1;  // 실패
}

위의 코드는 아래와 같은 제약사항을 가진다.

  • 배열 내에 중복된 원소가 없어야 한다.
  • 찾으려는 원소가 반드시 배열 내에 있어야 한다.

더 범용적인 방식

이제 소개하려는 방식은 좀 더 범용적으로 사용할 수 있다. 핵심적인 아이디어는 아래와 같다.

어떤 조건 P를 적용했을 때, true와 false의 경계를 찾는다.

예제를 중심으로 보자. 먼저 아래와 같은 배열을 가정하자.

1
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}

이제 조건 P를 “5 보다 크거나 같다” 라고 하면, 아래 배열을 다음과 같이 해석할 수 있다. t는 true, f는 false이다.

1
2
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}
 f, f, f, f, f, f, t, t, t, t, t, t

자 이제 f와 t의 경계를 정할 수 있게 되었으면, 아래와 같은 코드로 그 경계를 찾아낼 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
inline bool p(int m) {
  return m >= 5;
}

int bs(int v) {
  int lo = 0, hi = size_of_array-1;
  while (lo < hi) {
    int m = (lo+hi)/2;
    if (p(m)) hi = m;
    else lo = m + 1;
  }
  return lo;
}

위 코드의 특징은 p를 어떻게 정하는냐에 따라 활용법이 무궁무진하다는 점이다. p를 잘 설정할 경우 복잡한 문제도 해결이 가능하다.

다만 중요한 것은 p가 생성하는 true와 false의 경계가 딱 하나만 나타나야 한다.

경계에 대한 좀 더 알아보자

앞서 소개한 예제를 돌려 보면 경계 중에서 더 큰 원소를 찾게 된다.

1
2
3
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}
 f, f, f, f, f, f, t, t, t, t, t, t
                   !

처음 필자가 이 코드를 만났을 때는, 왜 경계 중 더 큰 원소가 찾아지는지가 무척 궁금했다. 이를 이해하기 위해서는 아래 사실들이 중요하다.

  • lo < hi 가 while loop의 조건임을 기억해야 한다. 즉 lo와 hi가 같아지는 순간에 while이 멈추게 된다.
  • 또 m을 구하는 과정에서 내림 연산이 사용된다.
  • m에서 조건 p를 만족했을 때, 경계는 항상 m보다 작은 곳에 있다. 즉 hi를 옮겨야 한다. m을 내림으로 구했으므로 hi = m으로 두면, 어떤 조건에서든 hi는 내림 하기 전 m보다 작아지게 된다.
1
2
3
 f, f, f, f, f, f, t, t, t, t, t, t
                !     !     !
                lo    m     hi
  • m에서 조건 p를 만족하지 않았을 때, 경계는 항상 m보다 큰 곳에 있다. 즉 lo를 옮겨야 한다. m을 내림으로 구했으므로 lo = m + 1으로 두면, 어떤 조건에서든 lo는 내림 하기 전 m보다 커지게 된다.
1
2
3
 f, f, f, f, f, f, t, t, t, t, t, t
       !     !     !
       lo    m     hi
  • 경계에서 lo와 hi만난다면 m은 내림하므로 lo와 같아진다. m에서는 조건을 만족하지 않는다. 결국 lo = m + 1이 되어서 경계 중 더 큰 원소에서 멈춘다.
1
2
3
4
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}
 f, f, f, f, f, f, t, t, t, t, t, t
                !  !
               lo  hi
  • m이 경계 중 아래 원소에 위치해서, lo가 경계보다 커졌다면, hi는 계속 감소해서 결국 lo와 같아진다.
1
2
3
4
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}
 f, f, f, f, f, f, t, t, t, t, t, t
                !  !              !
                m  lo             hi
  • hi는 결코 조건이 false 인 곳에 멈출 수 없다. false라면 항상 lo만 움직이기 때문이다.
1
2
3
4
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}
 f, f, f, f, f, f, t, t, t, t, t, t
             !  !
            lo  hi (impossible)

경계 중 아랫 원소에 멈추게 하기

그렇다면, 아래처럼 경계의 아래 원소를 찾기 위해서는 어떻게 해야 할까?

1
2
3
{1, 2, 3, 3, 3, 3, 5, 5, 6, 7, 8, 9}
 f, f, f, f, f, f, t, t, t, t, t, t
                !

가장 간단한 방법은 1을 빼서 return하는 것이다.

1
2
3
4
5
6
7
8
9
int bs(int v) {
  int lo = 0, hi = size_of_array-1;
  while (lo < hi) {
    int m = (lo+hi)/2;
    if (p(m)) hi = m;
    else lo = m + 1;
  }
  return lo - 1;
}

또 다른 방법은 m을 구할 때 올림을 하도록 하는 것이다.

1
2
3
4
5
6
7
8
9
int bs(int v) {
  int lo = 0, hi = size_of_array-1;
  while (lo < hi) {
    int m = (lo + hi + 1)/2;
    if (p(m)) hi = m - 1;
    else lo = m;
  }
  return lo;
}