[알고리즘][C++] 이진검색 (Binary Search)

개요

이진검색(Binary Search) 알고리즘은 정렬된 배열의 중간값과 찾고자 하는 키 값을 비교하여 배열의 절반만 확인하는 과정을 반복하여 키 값이 배열에 있는지 확인하는 검색 알고리즘이다.

검색을 진행하면서 생길 수 있는 경우의 수는 다음과 같다.
 
1. 키 값이 배열에 있을 경우
  1-1. key값과 mid값이 같을 때 : "찾았습니다!" 출력 후 종료
  1-2. key값이 mid값보다 클 때 : start = mid + 1 로 설정 후 함수 재호출
  1-3. key값이 mid값보다 작을 때 : end = mid - 1 로 설정 후 함수 재호출
 
2. 키 값이 배열에 없을 경우
  이러한 경우에는 배열에 원소가 한 개 남을 때까지 검색이 진행된다.
  즉, 함수의 맨 처음에 배열에 원소가 한 개 남았을 때 key값과 mid값을 비교하는 과정을 거쳐야 한다.

---

코드

void Binary_Search (int arr[], int start, int end, int key){
	if(start == end){
		if(key == arr[end]) cout << "찾았습니다!";
		else cout << "키 값이 배열에 없습니다.";
	}
	else {
		int mid = (end + start) / 2;
		if(key == arr[mid]) cout << "찾았습니다!";
		else if(key > arr[mid]) {		// 키 값이 배열의 중간 값보다 클 때
			start = mid + 1;
			Binary_Search(arr,start,end,key);
		}
		else{		// 키 값이 배열의 중간 값보다 작을 때
			end = mid - 1;
			Binary_Search(arr,start,end,key);
		}
	}
}

---

실행 결과

main 함수에 이것저것 추가해 주고 코드를 돌려보면 다음과 같이 잘 작동하는 것을 볼 수 있다.
 

---

분석

• 이진검색 알고리즘의 최악의 경우 수행시간은 $ \Theta (\mathrm{log_2}n)  $ 이다.