이분 탐색의 원리와 구현 방법

이분 탐색이란?

• 이분 탐색(Binary Search)는 탐색 기법 중 하나로, 어떠한 데이터 리스트 L이 존재할 때 어떤 두 점을 지정하여 그 중간값을 보고 찾는 데이터와 비교하여 각 점의 위치를 옮기는 방법이다.
• 해방 방법을 사용하면 리스트의 길이가 N 일때, 매 번 2배씩 탐색 범위가 좁아지기 때문에 최종적으로 $O(logN)$이 된다. 일반적으로 탐색에 소요되는 시간이 $O(N)$임을 생각하면 효율적인 방법이다.
• 시간적으로 더 효율적인 대신에 하나의 제한 조건이 있다. 바로 데이터 리스트가 정렬되어 있어야 한다는 것이다. 이는 이진 탐색이 찾는 데이터와 현재 데이터를 비교하여 대소 유무에 따라 다음 위치를 결정하는 것이기 때문이다.

 

 

예시 문제

• 예시 문제로 백준의 숫자 카드가 있다.

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

• 해당 문제는 데이터가 배열에 존재하는지 탐색만 하면 되지만 숫자 카드의 개수가 50만이고, 찾아야 하는 수들 역시 50만이 되어 각 요소들을 모두 탐색하는 일반적인 방법으로는 $O(N^2)$가 되어 시간 초과가 발생한다.
• 이를 이진 탐색으로 풀어보도록 하자. 먼저 배열을 정렬해야 한다. 이후 입력으로 들어온 존재 확인 값들에 대하여 이진 탐색을 수행 후 존재하면 1을 존재하지 않는다면 0을 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution2 {
    static int[] dataList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        dataList = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0; i < N; i++){
            dataList[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(dataList);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < M; i++){
            System.out.print(isExists(Integer.parseInt(st.nextToken())) + " ");
        }
    }

    static int isExists(int key){
        int left = 0;
        int right = dataList.length - 1;

        while(left <= right){
            int mid = (left + right) / 2;

            if (dataList[mid] == key){
                return 1;
            } else if (dataList[mid] < key){
                left = mid + 1;
            } else{
                right = mid - 1;
            }
        }

        return 0;
    }
}

• 가장 중요한것은 시작과 끝을 어떻게 잡을 것인지이다. 여기서는 배열 내부에 존재하는지를 보기 때문에 배열의 시작과 끝을 left와 right로 잡아 탐색을 진행한다.
• 만약 이 중간값이 key와 동일하다면 그대로 1을 반환하고, 그렇지 않다면 key가 중간값보다 큰지, 작은지에 대해서 비교를 시작한다.
• key가 중간값보다 크다면 다음 중간값은 최소한 지금 중간값보단 커져야 한다. 그렇다면 더 작은 부분이 올라와야 하기 때문에 left 가 mid + 1로 올라간다.
• key가 중간값보다 작다면 다음 중간값은 최소한 지금 중간값보단 작아야 한다. 그렇다면 더 큰 부분이 내려와야 하기 때문이 right가 mid - 1로 내려간다.
• 만약 left와 right가 교차한다면 배열 내부에 데이터가 없다는 것으로 0을 리턴하면 된다.