이분탐색 허벌나게 쉽게 구현(기억)하기

개요

이분탐색은 구현 시 늘 헷갈린다.

그래서 관련 자료를 찾던 중 아래 글을 보게 되었고, 내용을 정리한다.

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

전제

본 글에서는 lower bound, upper bound같은 통용되는 용어를 사용하지 않고,

왼쪽덩어리, 오른쪽덩어리라는 해괴망측한 용어를 사용하겠습니다

 

쉬운 이해를 위해서이니 양해를 부탁드립니다.

 

또, 모든 탐색 대상(배열)은 정렬되어있음을 가정합니다.

 

기본 틀

//정답의 범위가 A부터 B까지일 때
int left = A - 1, right = B + 1;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (왼쪽 덩어리에 들어갈 조건) left = mid;
    else right = mid;
}

 

모든 경우에... 기본 틀에서 세 가지만 수정하면 된다!

1. left초기값

2. right 초기값

3. 왼쪽덩어리에 들어갈 조건

 

 

위 코드를 실행하고 나면 반드시 아래 그림처럼 left와 right가 위치한다.

 

정답의 범위가 A부터 B까지일 때 (B포함), left는 A-1, right는 B+1에서 시작함을 유의해야 한다.

그래야 A와 B를 포함해서 탐색이 이루어질 수 있다.

 

배열같은경우 left의 초기값은 -1, right의 초기값은 array.length로 할당하면 된다.

 

예제 1

Q. 배열 { 1, 2, 3, 4, 5, 6, 7, 8, 9 } 에서 4를 찾으시오.

 

두 가지 방법으로 풀 수 있다.

A1. 왼쪽 덩어리에 4보다 작거나 같은 원소가 위치하도록 한 다음 arr[left]값을 보면 된다. (왼쪽 덩어리의 마지막)

A2. 왼쪽 덩어리에 4보다 작은 원소가 위치하도록 한 다음 arr[right]값을 보면 된다. (오른쪽덩어리의 처음)

 

int[] arr = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] < 4) left = mid; //4보다 작으면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(arr[right] + " at " + right); //4 at 3

int[] arr = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8, 9 };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] <= 4) left = mid; //4보다 작거나 같으면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(arr[left] + " at " + left); //4 at 3

예제 2

Q. 배열 { 1, 1, 3, 3, 5, 5, 7, 7 } 에서 4보다 큰값 중 가장 작은값(5)을 찾으시오.

 

 A. 마찬가지로 4를 기준으로 왼쪽덩어리 오른쪽덩어리를 구분해야 한다. 4보다 작거나 같으면 왼쪽 덩어리로 보낸 다음, 오른쪽덩어리의 처음을 보면 된다.

 

int[] arr = new int[]{ 1, 1, 3, 3, 5, 5, 7, 7 };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] <= 4) left = mid; //4보다 작거나 같으면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(arr[right] + " at " + right); //5 at 4

 

예제 3

Q. 배열 { 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4 } 에서 처음 나오는 2를 찾으시오

 

A. 2보다 작은걸 왼쪽덩어리, 나머지를 오른쪽덩어리에 넣고, 오른쪽덩어리의 첫 값(right값)을 보면 된다.

 

int[] arr = new int[]{ 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4 };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] < 2) left = mid; //2보다 작으면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(arr[right] + " at " + right); //2 at 3

 

예제 4

Q. 배열 { 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4 } 에서 마지막에 나오는 2를 찾으시오

 

A. 2보다 작거나 같은걸 왼쪽덩어리, 나머지를 오른쪽덩어리에 넣고, 왼쪽덩어리의 마지막 값(left값)을 보면 된다.

 

int[] arr = new int[]{ 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4 };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] <= 2) left = mid; //2보다 작으면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(arr[left] + " at " + left); //2 at 5

 

예제 5

Q. 배열 { true, true, true, false, false, false, false, false } 에서 처음 나오는 false를 찾으시오

 

A. true를 왼쪽덩어리, 나머지를 오른쪽덩어리에 넣고, 오른쪽덩어리의 첫값(left)을 보면 된다.

 

boolean[] arr = new boolean[]{ true, true, true, false, false, false, false, false };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid]) left = mid; //true면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(arr[right] + " at " + right); //false at 3

예제 6

Q. 배열 { 3,4,5,6,7 } 에서 1을 찾는다면 어떻게 되는가?

 

A. 1을 찾기 위해 두 덩어리를 나누면, 왼쪽 덩어리는 비어있을것이고 모두 오른쪽 덩어리에 위치할 것이다.

따라서 left는 -1, right는 0 값을 가진다.

 

int[] arr = new int[]{ 3,4,5,6,7 };

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] <= 1) left = mid; //true면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(left + " " + right); //-1 0

예제 7

Q. 배열 { 3,4,5,6,7 } 에서 9을 찾는다면 어떻게 되는가?

 

A. 9을 찾기 위해 두 덩어리를 나누면, 오른쪽 덩어리는 비어있을것이고 모두 왼쪽 덩어리에 위치할 것이다.

따라서 left는 4, right는 5 값을 가진다.

 

int left = -1, right = arr.length;
while (left + 1 < right) {
    int mid = (left + right) / 2;

    if (arr[mid] <= 9) left = mid; //true면 왼쪽덩어리로 보내버림
    else right = mid;
}

System.out.println(left + " " + right); //4 5

추신

left bound, right bound라는 용어로 인해 이분탐색이 헷갈려지는 경우가 많은 것 같다.

물론, 용어에게는 죄가 없고 죄는 나에게 있는 것이겠지만.... ^^7