이분 탐색

이분 탐색은 반으로 쪼개가면서 찾고자 하는 값을 얻어내는 방법

 

1부터 16 까지 16개 이므로 반으로 쪼개면 중간은 8입니다. 그리고 찾고자 하는 숫자는 8 이니 8 윗부분은 확인을 할 필요가 없어집니다.

 

이제 같은 방법으로 1~8 구간에서 반으로 쪼개면 4혹은 5가 되는데 아무 쪽으로 해도 큰 문제가 없으므로 거기서 또 분리를 하면 다음과 같습니다.

이제 남은 곳에서 반으로 쪼개게 되면 중간이 3이 되고 저희가 찾는 값에 도착하게 됩니다.

 

 

이렇게 보면 이진 / 이분 탐색이 아니라 그냥 탐색을 하게되면 최악의 경우 16번까지 다 확인을 해야하기 때문에 시간 복잡도가 O(n)이 나오게 됩니다. 그러나 이와 같이 이진 / 이분 탐색을 하게되면 3번만에 값을 찾을 수 있게 됨으로 최악의 경우라고 하면 O(logn)이 걸리게 됩니다.

 

따라서, 이진 / 이분 탐색트리는 반으로 쪼개가면서 값을 찾는 것을 의미하고 시간 복잡도는 O(logn) 입니다.