이분탐색1 이분탐색(Binary Search) 알고리즘 개요 이분탐색은 정렬된 데이터에서 검색 범위를 줄여나가며 원하는 데이터를 검색하는 알고리즘이다. 이진 탐색은 탐색을 반복할 때마다 탐색 범위를 반으로 줄인다. 탐색 범위가 1이 되는 최종 탐색 횟수를 k라고 하면, 1. 한 번 비교할 때의 범위는 n/2 2. 두 번 비교할 때의 범위는 n/4 3. 세 번 비교할 때의 범위는 n/8 ... k. k 번 비교할 때의 범위 n/(2^k)는 = 1 이고, k = log₂N 이다. 따라서 이진 탐색의 시간 복잡도는 O(logN)이 된다. 설명 0 1 2 3 4 5 6 7 8 9 2 5 6 9 12 13 14 18 20 23 위와 같이 정렬되어 있는 배열이 있을 때, 20을 찾는다고 가정해보자. 만약 순차탐색을 하면 0번째 인덱스, 1번째 인덱스, 2번째 인덱스 ... 2021. 10. 8. 이전 1 다음
