열혈 자료구조 - 1-2. 알고리즘의 성능 분석 방법(3)

이진 탐색 알고리즘의 시간복잡도

- 이진 탐색 알고리즘 : 순차 탐색보다 훨씬 좋은 성능을 보이지만 정렬되어 있어야 한다는 제약이 있음. 정렬의 기준은 상관 없음

- 이진 탐색 알고리즘의 순서

   -> 배열의 가운데 인덱스의 값에 대상이 있는지 확인

   -> 없다면 가운데 인덱스의 값과 대상을 비교하여 앞쪽을 찾을 지 뒤쪽을 찾을지를 결정(정렬되어 있다는 장점)

   -> 앞쪽에서 다시 가운데 인덱스와 대상을 비교하여 전의 과정을 반복

   -> 탐색을 반복할 수록 탐색 대상이 절반씩 줄게 됨

- 탐색 대상이 범위에 없다는 것을 판단하는 방법

   -> first와 last가 같을 경우가 없는 것이 아니라 이 경우에도 없으면 범위 없다고 생각해야 함

   -> first와 last가 역전되는 상황(first가 last보다 커지는 상황)이 범위에 없는 상황

int BSearch(int ar[], int len, int target) {
	int first=0;   // 탐색 대상의 시작 인덱스 값
	int last=len-1;   // 탐색 대상의 마지막 인덱스 값
	int mid; 

	while(first<=last) {
		mid=(first+last)/2;   // 탐색 대상의 중앙을 찾는다. 

		if(target==ar[mid]) {
			return mid;
		} // 중앙에 저장된 것이 타겟이라면
		else {
			if(target<ar[mid]) last=mid-1;   // 뒷부분을 탐색 대상에서 제외
			else		   first=mid+1;   // 앞부분을 탐색 대상에서 제외
		} // 타겟이 아니라면 
	}
	return -1;   // 찾지 못했을 때 반환되는 값 -1
} 

- 중심이 되는 연산 : '==' (탐색이기 때문에 확인하는 것이 중심)

- 시간 복잡도 (최악의 경우)

    -> n이 1이 될때까지 k번 비교하고 1이 됐을 때 1번 비교. T(n)=k+1

    -> n을 k번 1/2을 곱하여 1이된다는 식을 표현하고 그 식을 k에 대해 정리하면 아래와 같이 표현 가능

    -> $$T(n) = log_{2} (n) + 1$$이지만 +1은 큰 의미가 없기 때문에 생략하여 $$T(n) = log_{2} (n)$$이라고 표현 가능