Binary Search (이진 탐색)

이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 시간복잡도 O(log N) 만에 찾아내는 탐색하는 방법입니다.

오름차순으로 정렬된 사이즈가 N인 배열 D에서 원하는 값 k(k = 11)를 찾는 방법은 다음과 같습니다.

먼저 탐색할 데이터의 범위를 두 개의 인덱스(왼쪽, 오른쪽)로 지정하고 이를 L, R이라고 하겠습니다. 정렬되어있기 때문에 D[L]은 최솟값, D[R]은 최대값이 됩니다.

L			M				R
0	1	2	3	4	5	6	7
-3	0	1	4	7	9	11	16

당연히 처음 탐색 시에는 전체영역이므로 L = 0, R = N - 1 입니다. 이중 중앙값(Median)을 찾아 찾으려는 값 k와 비교합니다. 중앙값 M은 (L+R)/2 로 구할 수 있습니다.
중앙값인 D[M]과 K를 비교하였을 시, K가 더 크므로 [0, M]범위에는 K값이 존재할 수 없습니다. 그러므로 L을 M+1로 옮겨주어 [M+1,R] 사이에서 K값을 찾도록 해보겠습니다.

				L	M		R
0	1	2	3	4	5	6	7
-3	0	1	4	7	9	11	16

아직도 D[M]이 K보다 작기 때문에, L을 M+1로 옮겨주겠습니다.

						L / M	R
0	1	2	3	4	5	6	7
-3	0	1	4	7	9	11	16

D[M]이 K와 같으므로 원하는 값을 찾았습니다.

이와 같이, 중앙값(D[M])과 찾으려는 값을 비교하여 찾으려는 값이 중앙값보다 크다면 L = M + 1, 작다면 R = M - 1을 한 후 다시 M을 구하는 방법으로 찾으려는 값이 없는 범위를 절반씩 잘라가면서 구하는 방법이 이진 탐색입니다.

만약 찾으려는 값이 없다면 L > R이 되어서 종료하면 됩니다. 이 경우에도, 최대한 찾으려는 값과 비슷한 값들을 찾아가기 때문에, 이 점 또한 유용하게 사용하실 수 있습니다.

이 알고리즘의 시간복잡도는 쿼리당 O(log N)으로 빠른 알고리즘입니다. 정렬 알고리즘 또한 힙정렬이나 퀵정렬 등의 빠른 알고리즘을 사용하시면 더 효율적입니다.

다음은 C++로 나타낸 코드입니다.

#include <iostream>
#include <algorithm>

#define MAX 5005

int d[MAX], n;

bool bsearch(int val){

	int l = 0, r  = n - 1;

	while(l <= r){
		int mid = (l+r)/2;

		if(val == d[mid]) return true;
		else if(val > d[mid]) l = mid + 1;
		else r = mid - 1;
	}

	return false;
}

int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
		cin >> d[i];

	sort(d, d + n);

	int query;

	cin >> query;

	while (query--) {
		int x; cin >> x;

		if (bsearch(x)) cout << "exist" << endl;
		else cout << "not exist" << endl;
	}
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] d = new int[5005];
        for (int i = 0; i < n; i++)
            d[i] = scanner.nextInt();

        // bubble sorting
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (d[j] > d[j + 1]) {
                    int temp = d[j];
                    d[j] = d[j + 1];
                    d[j + 1] = temp;
                }

        // binary search for each query
        int query = scanner.nextInt();
        for (int i = 0; i < query; i++) {
            int x = scanner.nextInt();
            int l = 0, r = n - 1;
            boolean answer = false;

            while (l <= r) {
                int mid = (l + r) / 2;
                if (x == d[mid]) {
                    answer = true;
                    break;
                }
                else if (x > d[mid]) l = mid + 1;
                else r = mid - 1;
            }

            if (answer == true) System.out.println("exist");
            else System.out.println("not exist");
        }
    }
}