알고리즘 - 이분 탐색(Binary Search)

1. 지금까지 학습한 부분 정리 (자료구조)

• 스택 : 프링글스 통 (마지막에 넣은 게 먼저 나옴)
• 큐 : 놀이공원 줄 (먼저 온 사람이 먼저 나옴)
• 덱 : 양쪽이 뚫린 터널 (양방향 큐)

스택과 큐가 도구였다면, 이분 탐색은 그 도구를 효율적으로 다루는 지능이라고 할 수 있다.

 

2. 업-다운(Up-Down) 게임의 필승법

이분 탐색(Binary Search)은 술자리 게임인 업-다운 게임과 완벽하게 똑같다.

 

상황 : 1부터 100까지 숫자 중, 술래가 생각한 숫자(70)를 맞춰야한다.

1. 하수 (순차 탐색, O(N)) : 1 -> 2 -> 3 ...
2. 고수 (이분 탐색, O(log N)) : 중간을 찌름 (질문 한 번에 후보가 절반씩 소거된다.)

 

3. 조건 : 반드시 숫자가 순서대로 정렬이 되어야 한다.

이분 탐색 코드를 짤 때는 항상 정렬이 되어야 그 뒤에 절반씩 자를 수 있다.

 

4. 코드 구현

// 이미 정렬된 배열(arr)에서 target 찾기
public static int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {
        int mid = (start + end) / 2; // 정확히 중간 지점

        if (arr[mid] == target) {
            return 1; // 찾았다!
        } else if (arr[mid] < target) {
            start = mid + 1; // Up! (왼쪽 절반 버림)
        } else {
            end = mid - 1;   // Down! (오른쪽 절반 버림)
        }
    }
    return 0; // 끝까지 없으면 실패
}