이분 탐색, 그림으로 쉽게 이해하기

1. 이분 탐색 (binary-search)란 무엇인가요?

이분 탐색(binary-search)이란, 정렬된 상태의 일련의 데이터 중 현 기점에서 답 후보가 될 수 없는 절반을 삭제해가며 답을 찾아내는 탐색 알고리즘 이다.

다음과 같이 정렬된 10개의 정수가 배열 형태로 주어져 있다고 하자. 우리는 여기서 23이란 수를 찾고자 한다.

(1) 먼저 목표값과 비교할 기준을 구해야 한다. 기준은 항상 값을 구해야 하는 구간의 중앙값이다. (짝수면은 중앙의 두 개의 값 중 앞 쪽 값이다.)

(2) 16을 23과 비교해보니, 작다. 이 말은 즉 '16의 앞쪽 원소들도 목표 값보다 작다.' 는 말이 된다. 왜냐하면 이미 오름차순으로 정렬된 상태에서 탐색을 시작했기 때문이다. 따라서 16과 그 앞 쪽의 수들은 전부 날린다.

(3) 이제 남은 영역에서 다시 탐색한다. 탐색 과정은 (1)에서 (2)를 반복하면 된다. 여기서 중앙갑은56이고 23과 비교 하니 크다. 따라서 56과 그 이상의 값들은 삭제한다. 보지 않아도 거기서 답이 없다는 것을 안다.

(4) 23과 38의 중앙값을 구하니, 앞 쪽에 있는 23이 나왔다. 23은 우리가 구하려는 목표값과 같다. 값을 찾았음으로, 이분 탐색을 종료한다.

2. 어떻게 구현 하나요?

(1) 로직

(2) 구현

a. SUDO CODE

// 배열 내에서 타겟 값의 위치 찾기!
이분탐색(start, end, target)
    while(start <= end){
        // 중앙 값 구하기
        mid = start 와 end의 중간 index;
        if(mid가 가르키는 값이 목표값 보다 작다.) 중간값 상향 조정 필요. start = mid + 1 로 재조정;
        else 중간값 하향 조정 필요. end = mid - 1 로 재조정;
    }

    if(start가 가르키는 값 == target) return start;
    else return null;

b. 코드 Java

import java.io.*;
import java.util.ArrayDeque;


public class Main {
    public static void main(String[] args) throws IOException {
        int [] arr = new int []{10,15,38,39,45,72,89,95,100,102};
        System.out.println(binary_search(arr, 0, arr.length-1, 72));
    }
    public static int binary_search(int [] arr, int start, int end, int target){
        while(start <= end){
            int mid = start + (end - start)/2;
            if(arr[mid] < target) start = mid+1;
            else end = mid-1;
        }
        if(arr[start] == target) return start;
        else return -1;
    }
}

위 코드는 target 값의 index를 찾는 코드이다.

3. 이분탐색의 응용

최적화 문제를 풀 때, 이분 탐색을 응용 해야 한다.

최적화 문제 란?

문제에서 'A를 구하라', 'A가 있는지 없는지를 구하라'와 같이, 반환해야할 값이 하나의 값으로 명확한 문제를 결정 문제라 한다. 이와 다르게 '답이 될 수 있는 값 중 최소값 혹은 최대값을 구하라'와 같이, 답이 될 수 있는 복수의 값이 존재하고 그 중 문제에서 바라는 최적의 답을 구하는 것을 최적화 문제라고 한다.

기본적인 이분탐색 문제는 구하길 바라는 target값이 범주 내에 있는지 여부 혹은, 몇 번인지를 구하는 결정 문제였다. 반면 조건을 충족하는 수 중 최소값을 구하길 바라는 최적화 문제도 나올 수 있다.

이전엔 답을 충족하는 값을 만나면 바로 탈출해도 되었지만...

이제는 그럴 수 없다. 따라서 mid라는 포인터를 범주 끝에 다다르게 해줄 다른 방법을 사용해야 한다. 이러한 방법에는 LOWER BOUND와 UPPER BOUND가 있다.

(1) LOWER BOUND

mid 포인터가 가르키는 값이 target보다 크거나 같으면 하향조정하는 방식이다. 이때 같아도 하향조정 해버림으로, mid 포인터는 답이 될 수 있는 값 중 최소값에 종국에 다다르게 된다.

• (1) arr[mid] >= target: end = mid -1;
• (2) arr[mid] < target: start = mid + 1;

(2) UPPER BOUND

Lower Bound와 반대로, mid 포인터가 가르키는 값이 target보다 작거나 같으면 상향조정한다. 이렇게 하면 mid 포인터는 결국 Target 값보다 큰 값의 시작점을 가르키게 된다. (즉 답이 될 수 있는 최대값의 index + 1칸을 가리킴.)

• (1) arr[mid] <= target : start = mid + 1;
• (2) arr[mid] > target : end = mid - 1;