목록
728x90
이분탐색 (1)

얼음꽃의 일지

이분 탐색

이분 탐색은 반으로 쪼개가면서 찾고자 하는 값을 얻어내는 방법 1부터 16 까지 16개 이므로 반으로 쪼개면 중간은 8입니다. 그리고 찾고자 하는 숫자는 8 이니 8 윗부분은 확인을 할 필요가 없어집니다. 이제 같은 방법으로 1~8 구간에서 반으로 쪼개면 4혹은 5가 되는데 아무 쪽으로 해도 큰 문제가 없으므로 거기서 또 분리를 하면 다음과 같습니다. 이제 남은 곳에서 반으로 쪼개게 되면 중간이 3이 되고 저희가 찾는 값에 도착하게 됩니다. 이렇게 보면 이진 / 이분 탐색이 아니라 그냥 탐색을 하게되면 최악의 경우 16번까지 다 확인을 해야하기 때문에 시간 복잡도가 O(n)이 나오게 됩니다. 그러나 이와 같이 이진 / 이분 탐색을 하게되면 3번만에 값을 찾을 수 있게 됨으로 최악의 경우라고 하면 O(lo..
항해 일지 2022. 12. 18. 15:42
이전 Prev 1 Next 다음