이분 탐색(Binary Search)

데이터가 담긴 리스트를 탐색하는 방법은 크게 순차 탐색(Linear Search)과 이분 탐색(Binary Search)이 존재한다.

예를 들어 { 8, 3, 1, 5, 4, 7, 9, 2, 6, 10}, 10개의 데이터가 담긴 리스트가 있다고 하자. 이 리스트에서 9의 위치를 찾기 위해서는 어떻게 해야 할까?

위 리스트처럼 정렬되지 않은 리스트에서 데이터를 탐색하기 위해서는 어쩔 수 없이 처음부터 끝까지 순차적으로 탐색을 진행하여 9의 위치를 찾는 방법밖에 없을 것이다.

​그렇다면 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}처럼 정렬된 리스트가 있다고 생각해 보자. 이 리스트에서도 9의 위치를 찾기 위해서는 어떻게 해야 할까?

단순하게는 앞서 언급한 방법처럼 처음부터 순차적으로 9의 인덱스를 찾을 수 있다. 만약 1을 찾는다면 운이 좋게 한 번 만에 찾을 수 있지만, 10을 찾는 경우 리스트 전체를 탐색해야 한다. 따라서 평균적으로 O(N)의 시간 복잡도를 가진다.

​

이보다 효율적으로 탐색할 수 있는 방법은 없을까? 바로 이분 탐색이다. 이분 탐색은 리스트가 정렬되어 있다는 가정하에 O(log N)의 시간 복잡도로 탐색이 가능하게 해주는 효율적인 알고리즘이다.

이분 탐색은 우리가 영어사전에서 영어 단어를 찾을 때와 비슷한 원리라고 생각하면 이해하기 쉬울 것이다. 영어 단어를 찾을 때 우리는 처음부터 한 장씩 넘겨가며 탐색하지 않고, 우리가 원하는 영어 단어의 알파벳 순서를 기준으로 대략 어느 정도의 위치를 펼친 후 탐색할 것이다. 이와 비슷한 개념으로 이분 탐색은 주어진 리스트를 절반씩 나눠가며 원하는 데이터를 탐색하는 방법이다.

 

이분 탐색(Binary Search)은 정렬된 리스트를절반씩 나눠가며 탐색하는 알고리즘이다.

 

 

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}의 리스트에서 7의 위치를 이분 탐색을 통해 찾는 과정을 살펴보자.

이분 탐색은 리스트의 중간부터 시작한다. 5, 6둘 중 아무 데서나 시작해도 되지만 나는 5부터 시작하겠다.

중간부터 시작하여 mid의 값이 key보다 작으면 좌측에는 탐색할 필요가 없기 때문에 left를 mid+1로 바꿔주고, mid의 값이 key보다 크다면 우측에는 탐색할 필요가 없기 때문에 right를 mid-1로 바꿔주면서 탐색을 계속 진행한다.

만약 mid의 값이 key과 같으면 원하는 key 값을 찾았기 때문에 탐색을 종료한다. 만약 left > right라면 리스트에는 원하는 데이터가 없는 것이다.

 

위의 그림을 보면 7의 인덱스를 순차 탐색으로 찾을 경우 7번의 과정이 필요하지만, 이분 탐색으로 찾을 경우 4번의 과정으로 찾을 수 있다.

N이 10일때는 크게 차이가 안 느껴질 수 있지만 N이 무수히 크다면 두 탐색 알고리즘의 성능 차이는 월등하게 차이 날것이다. 이분 탐색은 매번 절반씩 나눠서 탐색하기 때문에 N이 100만이라 하여도 100만은 약 2^20이기 때문에 20번의 탐색 이내로 원하는 데이터의 위치를 찾을 수 있다.

이분 탐색(Binary Search)의 시간 복잡도는 O(log N)이다.

 

이분 탐색을 Java로 구현한 코드는 다음과 같다.

public static int binary_Search(int key, int left, int right, int[] list) {
	if (left <= right) {
		int mid = (left + right) / 2;
			
		if (list[mid] == key) {
			return mid;
		} else if (list[mid] > key) {
			return binary_Search(key, left, mid - 1, list);
		} else {
			return binary_Search(key, mid + 1, right, list);
		}
	}
	//리스트에 key값이 없음
	return -1; 
}