이진 탐색(binary search) 안 헷갈리게 구현하기

이진 탐색을 구현할 때 반복문의 조건을 어떻게 해야할지, mid값이 어떻게 되어야 하는지, 결국 답은 무엇인지 등등 헷갈리는 경우가 많다. 이를 헷갈리지 않고 정확히 구현하는 방법을 적어보겠다.

 

0. 탐색전에 해야할 것

탐색 구간이 연속 구간(e.g. 0~999의 자연수, -50~50의 정수)이라면 이 문단은 읽지 않아도 된다.

 

만약 연속 구간에서의 탐색이 아니라, 서로 다른 여러 개의 원소들 중에 하나를 택하는 경우라면 탐색할 원소들을 정렬할 것! 오름차순/내림차순 중 어느것으로 정렬할지는 문제에 따라 잘 선택하면 된다. "가장 큰/긴/무거운/느리게" 등이면 오름차순으로, "가장 작은/짧은/가벼운/빨리" 등이면 내림차순으로!

(e.g. {1, 5, 9, 8, 3, 7}의 원소 집합이 있을 때, 조건 A를 만족하는 가장 작은 원소를 구해야 한다면 9, 8, 7, 5, 3, 1 순으로 정렬한다.)

(e.g. {4, 9, 0.5, 2, 1.4, -5}kg의 물체가 있을 때, 조건 B를 만족하는 가장 무거운 물체를 구해야 한다면 -5, 0.5, 1.4, 2, 4, 9 순으로 정렬한다.)

 

1. 탐색 범위

탐색 범위를 의미하는 변수는 항상 [left, right)가 되도록 한다.

 

2. 반복문의 조건

left와 right 사이에 원소가 하나라도 있다면 반복문을 계속한다.

즉, [left, right)인데 원소가 하나라도 있다는 것은

... ㅁ ㅁ ㅁ left ㅁ right ㅁ ㅁ ... 이므로 left + 1 < right 를 의미한다. 

 

3. 반복문 내부

문제에 주어진 조건을 만족하는지 확인하는 것은 항상 중앙값(mid)이다.

즉 mid = (left + right) / 2이다.

만일 구하려는 조건을 mid값이 만족했다면 더 나은 해가 우측에도 있을 수 있다.

   => 따라서 탐색의 시작범위를 mid값으로 해서 이제 우측 구간을 탐색하도록 한다.

만족하지 못했다면 조건을 만족하는 해들은 mid보다 좌측에 있을 것이다.

   => 따라서 탐색의 끝 경계를 mid값으로 해서 좌측구간에서만 탐색하도록 한다.

정리하면

if (condition(mid)) left = mid;

else right = mid;

 

4. 답은?

반복문을 탈출하는 경우는 left와 right 사이에 원소가 하나도 없는 경우이다.

즉, 탐색 결과는 다음과 같이 나왔다는 것이다.

원소:                  ... ㅁ ㅁ ㅁ left right ㅁ ㅁ ...

조건 만족 여부:   o  o  o  o    o      x     x  x  x  

그럼 최적의 해는 바로? 반복문이 끝났을 때 left값이 된다.

 

5. Pseudocode

left = 가능한 최소 답;

right = 가능한 최대 답 + 1;

while (left + 1< right) {

    mid = (left + right) / 2;

    if (condition(mid)) left = mid;

    else right = mid;

}

정답 = left;