이분 탐색, 3분 안에 이해하기

정의

후보를 반으로 줄여가면서 답을 찾아가는 탐색 방법

(업다운 게임과 동일한 원리)

 

특징

낮은 시간복잡도 O(logN),
N은 탐색 대상인 원소의 개수 

 

기본 조건

정렬되어 있는 배열

 

규칙

*LOW : 가장 작은 인덱스
*HIGH : 가장 큰 인덱스
*MID : 중간 인덱스 (LOW + HIGH / 2)
*중간값 : 중간 인덱스에 해당하는 값 (arr[MID])

 

종료 조건

• 답이 중간값과 같으면 (답을 찾은 것)
• LOW와 HIGH가 역전 (답이 존재하지 않는 것)

두 가지 상황

• 답이 중간값보다 크면
  1. 후보를 중간 인덱스 이후로 한정한다. (LOW = MID + 1)
  2. MID 재설정
• 답이 중간값보다 작으면
  1. 후보를 중간 인덱스 이전으로 한정한다. (HIGH = MID - 1)
  2. MID 재설정

 

예시

 

코드 (Java)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31));
        Collections.sort(list);

        int targetIdx = binarySearch(list, 19);
        System.out.println("targetIdx = " + targetIdx);
    }

    public static int binarySearch(List<Integer> list, int target) {
        int low = 0, high = list.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // 오버플로우를 방지하기 위한 변형
            
            if (list.get(mid) < target) {
                low = mid + 1;
            } else if (list.get(mid) > target) {
                high = mid - 1;
            } else {
                return mid;
            }
        }

        return -1; // 해당 값이 존재하지 않을 때
    }
}

 

연습 문제

[Baekjoon Online Judge] 10815. 숫자 카드 (C++)