[알고리즘] BinarySearch

구현방식

* 배열이 sorting되있지 않을시 sort를 시켜야함 (sorting된 data structure를 대상으로 하는 알고리즘)

1. 시작 인덱스와 마지막 인덱스의 중간지점( (시작 인덱스 + 마지막 인덱스) / 2 ) 을 잡는다.

2. 찾으려는 Key값과 비교해서 탐색범위를 1/2로 줄인다.

3. 위와 같은 방법을 찾으려는 키값을 찾을때까지 재귀적으로 반복한다.

#include
using namespace std;
// Edited by Survivalking 2017 03 25

int binarySearch(int e[], int first, int last, int K)
{
	int index = 0;

	if (last < first) {
		cout << "값이 존재하지 않습니다." << endl;
		index = -1;
	}
	else
	{
		int mid = (first + last) / 2;
	
		if (e[mid] == K) {
			index = mid;
		}
		else if (e[mid] > K)
			index = binarySearch(e, first, mid - 1, K);
		else
			index = binarySearch(e, mid + 1, last, K);
	}
	return index;
}


int main()
{
	int temp[] = { 1,2,3,4,5,6,7,8,9,10 };
	int K;
	cout << "배열에서 찾을값 K를 입력해주시오 ";
	cin >> K;
	cout << "결과 : " << binarySearch(temp, 0, sizeof(temp) / sizeof(int) - 1, K) << endl;
	return 0;
}

찾으려는 키값이 없을경우 -1을 리턴하고 키값이 있을 경우 해당 키값의 인덱스를 출력하는 코드

알고리즘의 Worst-Case 분석

배열의 크기 : N

해당 알고리즘에서 탐색영역을 1/2씩 줄여나가고 최악의경우 탐색영역이 1보다 크거나 같을때 진행하게됩니다

계속 반복하게 되면 최종적으로

위와 같이되고

N을 이항시키고 로그를 취하게되면

그러므로 BinarySearch의 Worst-Case 시간복잡도는

입니다.

알고리즘의 Average-Case 분석