이진 탐색이란?
이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 매 단계마다 탐색 범위를 절반으로 줄이기 때문에, n개의 원소에서 최대 log₂(n)번의 비교만으로 원하는 값을 찾을 수 있습니다.
사전에서 단어를 찾을 때 처음부터 한 페이지씩 넘기지 않고, 중간을 펼쳐서 앞뒤를 판단하는 것과 같은 원리입니다.
왜 중요한가?
이진 탐색은 코딩 테스트에서 가장 자주 출제되는 알고리즘 중 하나입니다.
- •시간복잡도: O(log n) — 100만 개의 데이터에서 최대 20번만에 탐색
- •활용 범위: 배열 탐색, 파라메트릭 서치, Lower/Upper Bound
- •면접 빈출: Google, 카카오, 네이버 등 거의 모든 코딩 테스트에 출제
동작 원리
1단계. 배열의 중간 인덱스(mid)를 계산합니다.
2단계. 중간 값과 찾는 값(target)을 비교합니다.
- •target == arr[mid] → 찾음
- •target < arr[mid] → 왼쪽 절반으로 범위 축소
- •target > arr[mid] → 오른쪽 절반으로 범위 축소
3단계. 범위가 빌 때까지 반복합니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 (최선) | O(1) |
| 시간 (평균/최악) | O(log n) |
| 공간 (반복문) | O(1) |
| 공간 (재귀) | O(log n) |
매번 탐색 범위가 절반으로 줄어들기 때문에 O(log n)입니다. 10억 개의 데이터도 약 30번의 비교로 찾을 수 있습니다.
이진 탐색의 핵심 조건
반드시 정렬된 배열이어야 합니다. 정렬되지 않은 배열에서는 이진 탐색을 사용할 수 없습니다. 만약 정렬이 필요하다면 O(n log n)으로 먼저 정렬한 후 이진 탐색을 적용합니다.
실전에서 자주 나오는 변형
Lower Bound — target 이상인 첫 번째 위치를 찾습니다. 중복 값이 있을 때 유용합니다.
Upper Bound — target 초과인 첫 번째 위치를 찾습니다.
파라메트릭 서치 — "조건을 만족하는 최솟값/최댓값"을 이진 탐색으로 찾습니다. "나무 자르기", "랜선 자르기" 같은 문제가 대표적입니다.
자주 하는 실수
- •mid 계산 시 오버플로우:
(left + right) / 2대신left + (right - left) / 2사용 - •무한 루프: left, right 업데이트를 잘못하면 종료 조건에 도달하지 못함
- •정렬 확인 누락: 이진 탐색 전 배열이 정렬되어 있는지 반드시 확인
알고노트에서 직접 확인하세요
이진 탐색이 매 단계마다 어떻게 범위를 좁혀가는지, 알고노트에서 시각적으로 확인할 수 있습니다. 배열 크기와 target 값을 바꿔가며 실험해보세요.