Binary Search

이진 탐색 알고리즘에 관해 간단하게 포스팅해보려 합니다.

#include <stdio.h> 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; } int main(void){ int arr[] = {1, 3, 5, 7, 9}; int idx; idx = BSearch(arr, sizeof(arr)/sizeof(int), 7); if(idx == -1) printf("탐색 실패 \n"); else printf("타겟 저장 인덱스: %d\n", idx); idx = BSearch(arr, sizeof(arr)/sizeof(int), 4); if(idx == -1) printf("탐색 실패 \n"); else printf("타겟 저장 인덱스: %d\n", idx); return 0; }

위 소스에서 최악의 경우에 대한 시간 복잡도 함수는

k를 n이 1이 되기까지 2로 나눈 횟수라 할때  T(n) = k + 1 입니다.

n이 1이 되기까지 2로 나눈 횟수가 k이므로 다음과 같은 식도 세울수 있습니다.

저 식을 정리해주면

여기서 이 식에 로그를 취하고 정리해주면

따라서 결국

가 되는데 자료구조를 조금이라도 공부해보신 분이라면 알수 있는 내용이 

저 T(n) 구조를 취한 로그 그래프가 바로 x축을 데이터수라하고 y축을 연산횟수라 하였을때 

가장 바람직한 알고리즘이 된다는 것입니다.

결국 이진탐색알고리즘은 좋은 알고리즘!