이진 탐색

 

 

n개의 정렬된 원소들에서 특정 원소를 탐색하는 방법이다.

 

n개의 원소들의 n/2번째 인덱스에 해당하는 원소와 탐색을 원하는 원소의 크기를 비교하여

 

크기가 작다면 0부터 (n/2)-1까지의 인덱스에서만 탐색하면 된다.

 

 

 

 

시간복잡도 

 

탐색시간이 최대로 오래 걸릴 경우의 시간 복잡도는

 

(n)/(2^k)=1 일때의 k이므로 logn/log2==>logn이다.

 

 

 

효율성

 

정렬을 해야하므로 시간 복잡도가 nlogn이라고 생각할 수 있는데

 

매우 많이 찾아야할 때 한번 정렬을 하고 탐색하는 것이 그냥 무작정 처음부터 끝까지 찾는 것[O(n)]보다 효율적이다.

 

1000개의 원소를 10만번 탐색해야할 때 시간 효율성은

 

이진탐색 : 1000*(log1000)*(log1000)^10만 <<< 무작정 처음부터 찾는 탐색 : (1000)^10만

 

따라서 탐색 횟수가 적을때는 무작정 찾는 것이 효율적이고 

 

탐색횟수가 많거나 이미 정렬되어 있는 경우에는 이진탐색이 더 효율적이다.

 

 

 

이진탐색 구현

 

재귀함수를 구현방법과 반복문을 이용하여 구현한 방법 2가지가 존재한다.