Bin
SEARCHING
이진 탐색 (Binary Search)
정렬된 배열에서 중간값과 비교해 탐색 범위를 절반씩 줄여나가는 과정을 한 단계씩, 또는 자동 재생으로 직접 확인하세요. 목표값을 바꿔가며 최선·평균·최악의 경우 비교 횟수가 왜 다른지 눈으로 비교할 수 있습니다.
이진 탐색은 정렬된 배열을 전제로 합니다 — 배열은 항상 오름차순으로 고정되어 있습니다.
재생 버튼을 눌러 탐색을 시작하세요.
목표값 54 · 비교 0회
1 / 1
속도
제외됨
탐색 범위
비교 중 (mid)
발견!
PSEUDOCODE
lo ← 0, hi ← n-1while lo ≤ hi mid ← (lo + hi) / 2 if array[mid] == target: return mid else if array[mid] < target: lo ← mid + 1 else: hi ← mid - 1return -1 (찾지 못함)어떻게 동작하나요
정렬된 배열에서 탐색 범위(lo~hi)의 중간 인덱스 값을 목표값과 비교합니다. 중간값이 목표값보다 작으면 목표값은 오른쪽 절반에 있으므로 왼쪽 절반을 버리고, 크면 반대로 오른쪽 절반을 버립니다. 이렇게 매 비교마다 탐색 범위가 절반으로 줄어들기 때문에, 배열이 아무리 커도 소수의 비교만으로 답을 찾거나 없음을 확인할 수 있습니다.
시간·공간 복잡도
- 최선 (중앙값 적중)
- O(1)
- 평균 / 최악
- O(log n)
- 공간 복잡도
- O(1)
- 선행 조건
- 정렬된 배열
배열 10칸 기준 최악의 경우도 비교 4회면 충분합니다 — 직접 값을 입력해 확인해보세요.
그래프 탐색(BFS·DFS)도 이어서 시각화할 예정입니다 — Algorithm 코스로 돌아가기