[자료구조] 이진 탐색 (binary search)

배열의 요소가 많지 않다면 순차 탐색이 어느 정도 충분한 탐색 방식일 수 있습니다. 그렇지만 요소가 적지 않은 배열이라면 정렬되지 않은 상태에서 탐색을 하는 것은 비효율적입니다.

 

따라서 정렬을 먼저 한 다음 탐색을 하는 것이 효율적입니다. 그 중 이진 탐색을 먼저 살펴보겠습니다.

 

이진 탐색이란?

이진 탐색은 배열의 중앙에 있는 값을 선택해 찾고자 하는 값과 비교를 통해 탐색 범위를 반으로 줄이는 탐색 기법입니다. 데이터의 양이 많을 때 사용하면 탐색 횟수를 획기적으로 줄일 수 있습니다.

 

이진 탐색 구현

이진 탐색의 핵심은 반으로 나누기입니다.

 

과정은 아래와 같습니다.

1. 리스트의 가운데 있는 요소를 선택
2. 선택한 요소가 찾으려고 하는 값보다
   • 크면 왼쪽 리스트 탐색
   • 작으면 오른쪽 리스트 탐색
3. 찾으면 요소의 인덱스 return
4. 탐색해야 될 항목이 없으면 탐색 실패

 

이진 탐색은 재귀 혹은 반복문을 이용해 구현할 수 있습니다.

int binary_search_recursion(int key, int low, int high) {
	int middle;
	if(low <= high) {
		middle = (low + high) / 2;
		if(key == list[middle]) {
			return middle; // 탐색 성공
		} else if (key < list[middle]) { // 왼쪽 부분 리스트 탐색
			return binary_search_recursion(key, low, middle - 1);
		} else { // 오른쪽 부분 리스트 탐색
			return binary_search_recursion(key, middle + 1, high);
		}
	}
	return -1;
}

int binary_search_iter(int key, int low, int high) {
	int middle;
	while(low <= high) {
		middle = (low + high) / 2;
		if(key == list[middle]) {
			return middle;
		} else if (key > list[middle]) {
			low = middle + 1;
		} else {
			high = middle - 1;
		}
	}
	return -1;
}

 

이진 탐색 시간복잡도

탐색을 반복할 때마다 탐색 범위를 반으로 줄입니다. 따라서 시간복잡도는 $O(log \space n)$이 됩니다.