- 목표값
- 남은 후보
- 비교 중
- 제외됨
- 찾음
이진 탐색
이진 탐색은 항상 가운데를 확인하는 방식으로 정렬된 목록에서 값을 찾습니다. 가운데 값이 너무 작으면 목표값은 그 뒤에만, 너무 크면 그 앞에만 있을 수 있습니다. 어느 쪽이든 남은 부분의 절반이 제외됩니다. 찾을 값을 고르고 탐색을 한 단계씩 진행하면서, 목표값을 찾거나 아무것도 남지 않을 때까지 음영 부분이 줄어드는 모습을 지켜보세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을, 음영 부분은 그 값이 아직 있을 수 있는 범위를 나타냅니다. 이진 탐색은 정렬된 목록이 필요하므로, 정렬되지 않은 목록은 먼저 정렬합니다. 찾을 값과 막대 개수를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 찾을 값과 막대 개수를 고르세요. 직접 숫자를 입력해도 됩니다. 이진 탐색이 먼저 정렬합니다.
- ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
- 끝에 가까운 값이나 목록에 없는 값으로 ‘비교’ 타일과 ‘선형 탐색이라면’ 타일을 비교해 보세요.
이진 탐색의 원리
정렬된 목록에서 아직 목표값이 있을 수 있는 부분을 기억해 둡니다. 처음에는 목록 전체입니다. 그 부분의 가운데 값을 봅니다. 목표값과 같으면 끝입니다. 더 작으면 목표값은 그 뒤에만 있을 수 있으므로 가운데 뒤쪽 부분에서 계속합니다. 더 크면 앞쪽 부분에서 계속합니다. 아무것도 남지 않으면 목표값은 목록에 없습니다.
왜 이렇게 빠를까
비교할 때마다 남은 부분이 절반으로 줄어듭니다. 값 n개에서 시작하면 k번 비교한 뒤에는 최대 약 n/2ᵏ개가 남으므로, 탐색은 최대 ⌊log₂ n⌋ + 1번 비교하면 끝납니다. 값 40개는 6번, 1,000개는 10번, 백만 개는 20번입니다. 선형 탐색은 모든 값을 확인해야 할 수도 있습니다. 다만 목록이 정렬되어 있어야 하고, 정렬 상태를 유지하거나 먼저 정렬하는 데도 비용이 듭니다.
자주 묻는 질문
이진 탐색은 어떻게 동작하나요?
정렬된 목록에서 아직 목표값이 있을 수 있는 부분의 가운데 값과 목표값을 비교합니다. 같으면 찾은 것이고, 아니면 목표값이 있을 수 없는 절반을 버리고 나머지 절반에서 탐색을 계속합니다. 목표값을 찾거나 아무것도 남지 않을 때까지 반복합니다.
이진 탐색은 비교를 몇 번 하나요?
값이 n개인 목록이면 최대 ⌊log₂ n⌋ + 1번입니다. 40개는 6번, 1,000개는 10번, 백만 개는 20번입니다. 비교할 때마다 남은 부분이 절반으로 줄어듭니다.
이진 탐색에는 왜 정렬된 목록이 필요한가요?
정렬된 목록에서만 비교 한 번으로 목표값이 어느 쪽에 있는지 알 수 있기 때문입니다. 정렬되지 않은 목록에서는 가운데 값이 더 작아도 목표값의 위치를 알 수 없으므로 아무것도 제외할 수 없습니다.
중복된 값이 있으면 어느 것을 찾나요?
가운데가 어디에 오느냐에 따라 그중 아무 하나를 찾습니다. 일치한 뒤에도 왼쪽이나 오른쪽으로 계속 탐색하는 변형은 첫 번째나 마지막 위치를 찾습니다.
제 숫자가 어딘가로 전송되나요?
아니요. 탐색은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동