정의
정렬된 배열에서 찾고자 하는 값의 위치를 빠르게 찾는 알고리즘입니다. 매번 탐색 범위를 절반으로 줄여서 찾기 때문에 매우 빠릅니다.
핵심 특성
- ✓전제조건: 배열이 반드시 정렬되어 있어야 함
- ✓매 단계마다 탐색 범위가 절반으로 줄어듦
- ✓100만 개 데이터도 약 20번 비교로 찾음
- ✓추가 메모리 불필요 (제자리 탐색)
활용 사례
이런 상황에서 사용됩니다:
📖
사전 찾기
두꺼운 사전에서 단어를 찾을 때, 중간 페이지를 펴서 앞/뒤로 이동하는 것과 같은 원리
🎮
게임 랭킹 검색
수백만 명의 게이머 중 특정 점수대의 플레이어를 빠르게 찾기
📚
도서관 책 찾기
정리된 도서관에서 청구기호로 책을 찾는 것처럼
주요 연산
주요 연산들:
탐색
O(log n)배열에서 특정 값의 인덱스를 찾습니다. 없으면 -1 반환.
복잡도
시간 복잡도
최선
O(1)
평균
O(log n)
최악
O(log n)
공간 복잡도
O(1)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기