이진 탐색(Binary Search)

이진 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 알고리즘이다. 이 알고리즘은 탐색 범위를 매 단계마다 절반으로 줄여 효율적으로 값을 얻는다.

이진 탐색의 특징

1. 데이터가 반드시 정렬되어 있어야 한다.
2. 데이터의 크기가 클수록 성능 이점이 두드러진다.
3. 삽입/삭제가 빈번히 이루어지는 데이터에는 적합하지 않다.(정렬 상태 유지 비용 발생)

작동 원리

1. 초기 설정: 배열의 시작 인덱스와 끝 인덱스를 설정한다.
2. 중간점 계산: 시작과 끝 인덱스의 중간점(mid)를 구한다.
3. 비교
   • list[mid] == key: 값을 찾았으면 mid 반환
   • list[mid] < key: 찾는 값이 오른쪽에 있으므로, low = mid + 1로 업데이트
   • list[mid] > key: 찾는 값이 왼쪽에 있으므로, high = mid - 1로 업데이트
4. 위 과정을 반복

전체 코드

순환 호출을 사용하는 이진 탐색

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

반복을 이용한 이진 탐색

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

시간 복잡도

이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄이기 때문에, 시간 복잡도는 다음과 같이 계산된다.

• 최악의 경우: $O(logn)$
• 최선의 경우: $O(1)$
• 평균적인 경우: 대부분의 경우 $O(logn)$의 성능을 가진다.

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구