BINARY SEARCH

사전 한가운데 펼치기 — 정렬 전제가 함정 1순위

동작 원리

중간 값을 본다 → 크면 앞쪽 절반, 작으면 뒤쪽 절반으로 범위를 줄여 반복. O(log n) — 100개도 약 7번.

📖

두꺼운 사전 — 첫 장부터 넘기지 않고 딱 중간을 펼쳐 앞/뒤 절반을 버림. 한 번에 후보가 절반씩 줄어듦.

⚠ 시험 함정 1순위

'정렬 안 된 데이터에서도 빠르다' · '순서와 무관하게 O(log n)' 보기는 모두 함정 — 정렬돼 있을 때만 동작. '이분 탐색' 보이면 '정렬' 단어부터 확인.