[자료구조(C언어)] 이진검색

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

많은 프로그램에서 가장 높은 빈도로 수행되는 알고리즘으로 이진검색과 정렬을 꼽을 수 있다.

 

이진검색

순차검색은 입력데이터가 배열이나 연결리스트 등일 때 실행할 수 있고, 앞에서부터 순차적으로 검색하는 것이다. 최악의 경우 시간복잡도는 O(n)이다.

이진검색(Binary Search)은 정렬된 배열에 대해서만 실행할 수 있다. (연결리스트에서는 이진검색을 할 수 없다. 가운데 데이터를 O(1)시간에 읽을 수 없기 때문이다.)

예를 들어 배열에 데이터들이 오름차순으로 정렬되어 저장되어 있을 때,

배열의 가운데에 있는 데이터를 내가 찾는 데이터와 비교한다.

가운데 데이터가 내가 찾는 데이터보다 작다면 뒤쪽에서만 검색한다.

이런 식으로 계속 범위를 반으로 좁혀나가는 방식으로 검색하는 것이 이진검색이다.

 

코드로 나타내면 다음과 같다.

int binarySearch(int n, char *data[], char *target) {
	int begin = 0, end = n-1;
	while (begin <= end) {
		int middle = (begin + end)/2;
		int result = strcmp(data[middle], target);
		if (result == 0)
			return middle;
		else if (result < 0)
			begin = middle + 1;
		else 
			end = middle - 1;
	}
	return -1;
}

한 번 비교할 때마다 남아있는 데이터가 절반으로 줄어든다.

따라서 시간복잡도는 O(log⑵n)이다.

 

순차검색의 시간복잡도인 O(n)과 이진검색의 시간복잡도인 O(log⑵n)의 차이는 매우 크다.

만약 데이터의 개수가 1000개라면, 순차검색은 최악의 경우 1000번(n번) 비교연산을 해야하지만 이진검색은 10번정도면 찾을 수 있다.

따라서 이진검색을 할 수 있는 상황(데이터가 배열에 정렬되어있을 때)에서 순차검색을 하는 것은 바람직하지 않다.