이진 탐색(Binary Search)에 대해 알아보자

이진탐색은 이전에 다룬 탐색방법과는 다르게 이미 정렬되어 있는 숫자에서 특정 숫자를 빨리 찾는 것이 목표인 알고리즘이다. 대상 데이터 전체의 중간값과 찾고자 하는 값을 비교해 찾고자 하는 값이 크면 중간값 오른쪽으로 범위를 좁히고 작으면 왼쪽으로 범위를 좁히는 것을 반복하며 원하는 값이 중간값으로 나올 때까지 반복하는 것이다. 시간복잡도는 O(logN)이며 구현이 매우 간단한 편이다.

구현은 투포인터와 유사하게 하면 된다. 시작포인터와 끝포인터를 처음에는 배열 전체의 시작과 끝으로 하고 중간값과 찾고자 하는 값을 비교해 중간값이 크면 끝포인터를 중간값-1로 바꾸어 중간값 왼쪽 데이터를 선택하고 중간값이 작으면 시작포인터를 중간값+1 해서 오른쪽 데이터를 선택하면 된다. 이것을 while문으로 반복하고 시작포인터가 끝포인터보다 작거나 같을 때만 반복시키면 된다. 만약 찾고자 하는 값이 없다면 시작포인터가 끝포인터보다 크게 될 것이다. 그러면 반복문에서 빠져나오게 되고 정답변수에 값이 있으면 출력하고 없으면 답이 없다고 출력해 주면 된다.

자바에는 이진탐색을 이용한 이진트리 자료구조가 존재한다.(사실 레드블랙트리이다) 만약 배열을 쓰기 싫다면 이진트리구조에 데이터를 넣어주기만 하면 따로 정렬할 필요도 없이 알아서 정렬도 해주고 원하는 값도 찾아주기까지 하니 적극적으로 사용해 보자. 트리구조의 비대칭 가능성도 레드블랙트리는 없애주기에 시간복잡도도 가장 최적의 경우로 가까워진다. 다음은 백준 1920번 원하는 정수 찾기 문제를 이진탐색으로 풀어본 것이다.

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

1920번: 수 찾기

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter((new OutputStreamWriter(System.out)));
        StringTokenizer st;
        TreeSet<Integer> tree = new TreeSet<>();
        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++){
            tree.add(Integer.parseInt(st.nextToken()));
        }
        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<M;i++){
            int find = Integer.parseInt(st.nextToken());
            int search;
            try {
                search = tree.ceiling(find);
            } catch(NullPointerException e){
                search = find + 1;
            }
            if(find==search) bw.write("1\n");
            else bw.write("0\n");
        }
        bw.flush();
        bw.close();
    }
}

데이터를 입력하는 부분부터 이진트리에 넣어줬고 찾는것은 해당 숫자가 없으면 바로 위의 숫자를 리턴하기 때문에 예외처리로 위에가 없을 경우도 해주었다. 그리고 원래 찾고자 하는 숫자와 찾은 숫자가 일치하는지 아닌지 검사하면 된다.

이진탐색은 매우 간단하지만 많은 곳에서 응용이 가능하다. 꼭 정확하게 이해하고 넘어가자.