정렬된 정수 배열을 입력으로 하는 이진 탐색 알고리즘에 대한 시간 복잡… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

정렬된 배열의 이진 탐색은 $O(\log_2(n))$이다.
비교할 때마다 탐색 구간이 절반으로 줄어 $n \to n/2 \to n/4 \to \cdots \to 1$이 되므로, 최악에도 약 $\log_2 n$회 비교로 끝난다. 점화식은 $T(n)=T(n/2)+O(1)$이다.
$O(n)$은 처음부터 하나씩 확인하는 순차 탐색의 복잡도다.
$O(n\log_2(n))$은 병합 정렬·힙 정렬 같은 비교 정렬의 복잡도다.
$O(n^2)$은 삽입·선택 정렬 등의 최악 복잡도로 탐색과 무관하다.