개념과 작동 원리
선형 탐색은 값을 차례로 확인하고 이진 탐색은 현재 구간의 중간값을 봅니다. 중간값보다 작거나 큰지를 알면 정렬 순서를 이용해 한쪽을 버릴 수 있습니다.
다음 비교에서도 정답이 있다면 남은 구간 안에 있다는 조건을 유지합니다. 구간이 비면 없는 값이라는 결론을 내립니다.
관계식과 성립 조건
후보가 대략 n/2ᵏ로 줄어들므로 필요한 비교는 로그 규모입니다. 실험의 n≥1인 중복 없는 목록에서는 최대 비교 횟수를 ⌊log₂n⌋+1로 비교할 수 있습니다.
정렬 비용은 탐색 비용과 별도로 생각해야 합니다. 중복값이 있는 목록에서 첫 위치·마지막 위치를 찾는 문제는 종료 조건을 조정해야 합니다.
가상 실험에서 읽을 변화
이진 탐색은 비교할 때마다 후보 범위를 절반으로 줄여요.
중복 없는 정렬된 정수 목록이에요. 선형 탐색도 같은 목록을 사용해요.
핵심 관계와 기호
binary steps ≤ ⌊log₂n⌋ + 1
| 기호 | 뜻 | 단위 |
|---|---|---|
| n | 데이터 개수 | 개 |
| k | 비교·범위 축소의 횟수 | 회 |
예시로 확인하기
이진 탐색에 필요한 조건은?
목록이 정렬돼 있어요 · 이진 탐색은 비교할 때마다 후보 범위를 절반으로 줄여요.
자주 헷갈리는 점
- 정렬되지 않은 목록에 중간값 비교 규칙만 적용한다고 올바른 이진 탐색이 되지는 않습니다.