13. 이분 탐색 (Binary Search)

이진 탐색이라고도 부르는 이분 탐색은 간단하면서도 강력한 알고리즘입니다. 기본적인 알고리즘의 아이디어는 이미 정렬이 되어 있는 자료구조에서 특정 값을 찾을 때에 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것입니다. 절반씩 나눠가면서 탐색하는 것에서 이분 탐색이라는 이름이 나왔다는 것을 알 수 있습니다. 

이진 탐색 - 나무위키

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

예를 들어 설명해보도록 하겠습니다.

아래와 같이 배열이 하나 주어졌다고 해봅시다.

0	1	2	3	4	5	6	7	8	9
2	5	6	10	12	13	15	17	19	23

여기서 우리가 알고 있는 것은 이 배열이 작은 수부터 큰 수까지 오름차순으로 정렬이 되어 있다는 것 뿐이고, 실제로 어떤 수가 어느 자리에 배치되어 있는지는 전혀 알 수 없는 상태라고 가정해보겠습니다. 이런 경우 숫자 하나를 던져줬을 때 그 숫자가 이 배열에 속하는지 어떻게 알 수 있을까요. 만일 이분 탐색을 사용하지 않는다면 for문을 이용해서 하나씩 확인해야할 것입니다. 원하는 숫자가 나오는 지점까지 확인해야하고 만일 그 숫자보다 큰 숫자가 나왔을 때 비로소 그 숫자가 배열에 포함되지 않았다는 사실을 알 수 있게 될 것입니다. 만일 그 숫자가 배열 맨 마지막에 있었다면 우리는 포함여부를 확인하기 위하여 쓸데 없는 탐색작업을 반복해야할 것입니다. 이러한 수고를 덜어줄 수 있는 것이 이분 탐색입니다. 

위 표를 이용하여 이분 탐색이 어떻게 이루어지는지 확인해보겠습니다. 예를 들어 포함여부를 확인해야하는 숫자가 17이라고 해봅시다. 우리는 배열이 0에서 9까지 사용되고 있다는 것을 알기 때문에 (0 + 9) / 2 계산을 통해 중앙값을 찾아줄 수 있습니다. 중앙값은 4가 될 것입니다. 나머지는 버리도록 하겠습니다. 이때 배열에서 4에 해당하는 값은 12라는 것을 알 수 있습니다.

0	1	2	3	4	5	6	7	8	9
2	5	6	10	12	13	15	17	19	23

우리가 원하는 값은 17이기 때문에 12보다는 우측에서 17이 있는지 확인해야할 것입니다. 그렇다면 제일 작은 위치값인 0을 버리고 중앙값 4에서 1을 더한 5를 최소 위치값으로 선정하여 위와 동일하게 다시 중앙값을 찾는 연산을 해줍니다. (5 + 9) / 2의 연산을 통해 이번에는 중앙값이 7이라는 것을 알 수 있습니다.

0	1	2	3	4	5	6	7	8	9
2	5	6	10	12	13	15	17	19	23

7이라는 위치의 값을 확인해보니 17입니다. 우리가 원하는 숫자가 배열에 포함되어 있다는 것을 확인할 수 있었습니다. 만일 단순하게 for를 이용해서 탐색했다면 적어도 0 ~ 7까지는 탐색해야했을 것이고 여덟 번의 탐색이 필요했을 문제를 두 번의 탐색만으로 찾아낼 수 있었습니다. 바로 이것이 이분 탐색의 장점이라고 할 수 있습니다. 

이제 실제 문제를 풀이하면서 이분 탐색을 익히도록 하겠습니다.

1920번: 수 찾기 - Baekjoon Online Judge

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

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

		int[] A = new int[N];
		for (int i = 0; i < N; i++)
			A[i] = Integer.parseInt(st.nextToken());

		Arrays.sort(A);

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

		for (int i = 0; i < M; i++) {
			int n = Integer.parseInt(st.nextToken());
			System.out.println(binarySearch(A, n));
		}
	}

	private static int binarySearch(int[] A, int n) {
		int first = 0;
		int last = A.length - 1;
		int mid = 0;

		while (first <= last) {
			mid = (first + last) / 2;

			if (n == A[mid])
				return 1;
			else {
				if (n < A[mid])
					last = mid - 1;
				else
					first = mid + 1;
			}
		}
		return 0;
	}
}