비교
남은 후보
선형 탐색이라면

  • 목표값
  • 남은 후보
  • 비교 중
  • 제외됨
  • 찾음

이진 탐색 자세히 알아보기

이진 탐색

이진 탐색은 항상 가운데를 확인하는 방식으로 정렬된 목록에서 값을 찾습니다. 가운데 값이 너무 작으면 목표값은 그 뒤에만, 너무 크면 그 앞에만 있을 수 있습니다. 어느 쪽이든 남은 부분의 절반이 제외됩니다. 찾을 값을 고르고 탐색을 한 단계씩 진행하면서, 목표값을 찾거나 아무것도 남지 않을 때까지 음영 부분이 줄어드는 모습을 지켜보세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을, 음영 부분은 그 값이 아직 있을 수 있는 범위를 나타냅니다. 이진 탐색은 정렬된 목록이 필요하므로, 정렬되지 않은 목록은 먼저 정렬합니다. 찾을 값과 막대 개수를 고르거나 직접 숫자를 입력하세요. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

작동 원리

  1. 찾을 값과 막대 개수를 고르세요. 직접 숫자를 입력해도 됩니다. 이진 탐색이 먼저 정렬합니다.
  2. ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 한 단계씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
  3. 끝에 가까운 값이나 목록에 없는 값으로 ‘비교’ 타일과 ‘선형 탐색이라면’ 타일을 비교해 보세요.

이진 탐색의 원리

정렬된 목록에서 아직 목표값이 있을 수 있는 부분을 기억해 둡니다. 처음에는 목록 전체입니다. 그 부분의 가운데 값을 봅니다. 목표값과 같으면 끝입니다. 더 작으면 목표값은 그 뒤에만 있을 수 있으므로 가운데 뒤쪽 부분에서 계속합니다. 더 크면 앞쪽 부분에서 계속합니다. 아무것도 남지 않으면 목표값은 목록에 없습니다.

왜 이렇게 빠를까

비교할 때마다 남은 부분이 절반으로 줄어듭니다. 값 n개에서 시작하면 k번 비교한 뒤에는 최대 약 n/2ᵏ개가 남으므로, 탐색은 최대 ⌊log₂ n⌋ + 1번 비교하면 끝납니다. 값 40개는 6번, 1,000개는 10번, 백만 개는 20번입니다. 선형 탐색은 모든 값을 확인해야 할 수도 있습니다. 다만 목록이 정렬되어 있어야 하고, 정렬 상태를 유지하거나 먼저 정렬하는 데도 비용이 듭니다.

자주 묻는 질문

이진 탐색은 어떻게 동작하나요?

정렬된 목록에서 아직 목표값이 있을 수 있는 부분의 가운데 값과 목표값을 비교합니다. 같으면 찾은 것이고, 아니면 목표값이 있을 수 없는 절반을 버리고 나머지 절반에서 탐색을 계속합니다. 목표값을 찾거나 아무것도 남지 않을 때까지 반복합니다.

이진 탐색은 비교를 몇 번 하나요?

값이 n개인 목록이면 최대 ⌊log₂ n⌋ + 1번입니다. 40개는 6번, 1,000개는 10번, 백만 개는 20번입니다. 비교할 때마다 남은 부분이 절반으로 줄어듭니다.

이진 탐색에는 왜 정렬된 목록이 필요한가요?

정렬된 목록에서만 비교 한 번으로 목표값이 어느 쪽에 있는지 알 수 있기 때문입니다. 정렬되지 않은 목록에서는 가운데 값이 더 작아도 목표값의 위치를 알 수 없으므로 아무것도 제외할 수 없습니다.

중복된 값이 있으면 어느 것을 찾나요?

가운데가 어디에 오느냐에 따라 그중 아무 하나를 찾습니다. 일치한 뒤에도 왼쪽이나 오른쪽으로 계속 탐색하는 변형은 첫 번째나 마지막 위치를 찾습니다.

제 숫자가 어딘가로 전송되나요?

아니요. 탐색은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 저장됩니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

편집기로 이동