이진탐색 시각화
정렬된 배열에서 절반씩 범위를 줄여 목표값을 찾는 O(log n) 탐색 과정을 관찰합니다
탐색★☆☆
속도
1 / 1비교 횟수: 0남은 범위: 30제거된 수: 0
탐색 대상:
배열 크기30
탐색 범위중간값제거됨발견!낮은 경계 (L)높은 경계 (H)
각 단계에서 중간값과 목표값을 비교하여 탐색 범위가 절반씩 줄어드는 것을 확인하세요.
이진탐색이란?
이진탐색(Binary Search)은 정렬된 배열에서 목표값을 찾을 때 매 단계마다 탐색 범위를 절반으로 줄이는 알고리즘입니다. 시간 복잡도 O(log n)으로 선형 탐색(O(n))보다 훨씬 빠릅니다. 1,000개 배열이면 최대 10번, 1,000,000개도 최대 20번이면 찾을 수 있습니다.
사용 방법
- 1배열 크기를 슬라이더로 조절하세요 (10~100)
- 2탐색 대상 숫자를 직접 입력하거나 '랜덤 대상' 버튼을 누르세요
- 3'새 배열 생성'으로 다른 정렬된 배열을 만들 수 있습니다
- 4재생 버튼으로 탐색 과정을 단계별로 관찰하세요
- 5노란색 블록이 현재 중간값(mid), 파란색이 탐색 범위, 회색이 제거된 범위입니다
동작 원리
- 1정렬된 배열에서 left=0, right=n-1로 탐색 범위를 초기화합니다.
- 2mid = (left + right) / 2를 계산하고 arr[mid]와 target을 비교합니다.
- 3arr[mid] === target이면 탐색 성공, arr[mid] < target이면 left = mid + 1 (오른쪽 절반), arr[mid] > target이면 right = mid - 1 (왼쪽 절반)으로 범위를 좁힙니다.
- 4left > right가 되면 탐색 실패로 배열에 값이 없음을 의미합니다. 매 단계마다 탐색 범위가 절반으로 줄어 O(log n) 복잡도를 달성합니다.
실무 활용
- •데이터베이스 인덱스(B-Tree)의 탐색 기본 원리로, 수억 건의 레코드에서 O(log n)으로 조회합니다.
- •사전/전화번호부 검색(알파벳 순 정렬)과 Git bisect를 통해 버그 도입 커밋을 이진탐색으로 찾습니다.
- •게임의 히트박스 판정에서 정렬된 좌표 검색과 프로그래밍 대회의 이분 탐색(parametric search)에 활용됩니다.
- •라이브러리 함수(Python bisect, Java Arrays.binarySearch, C++ std::lower_bound)로 제공되어 실무에서 자주 사용됩니다.
비슷한 알고리즘
- •선형 탐색 O(n) vs 이진탐색 O(log n) — 100만 개 배열에서 선형은 최대 100만 번, 이진탐색은 최대 20번만 비교합니다.
- •보간 탐색(Interpolation Search) — 값 분포가 균등할 때 O(log log n)으로 더 빠르지만, 분포가 불균일하면 O(n)으로 나빠집니다.
- •해시 탐색 O(1) — 단일 키 조회는 더 빠르지만 범위 검색, 순서 기반 조회는 불가합니다.
학습 팁
- •배열에 없는 값을 탐색해보면 탐색 범위가 완전히 줄어드는 것을 볼 수 있습니다
- •배열 크기를 2배로 늘려도 비교 횟수가 1번만 늘어나는 것을 확인하세요
- •L(low)과 H(high) 포인터가 교차되면 탐색이 종료됩니다
- •정렬되지 않은 배열에는 이진탐색을 사용할 수 없습니다
자주 묻는 질문
Q. 왜 정렬된 배열에서만 사용할 수 있나요?
A. 이진탐색은 중간값보다 목표값이 크면 오른쪽에 있다고 가정합니다. 정렬되지 않으면 이 가정이 틀려 잘못된 결과가 나옵니다.
Q. 시간 복잡도 O(log n)이 왜 빠른가요?
A. n=1,000,000이면 선형탐색은 최대 1,000,000번, 이진탐색은 최대 20번(log₂(1,000,000)≈20)만 비교합니다.
Q. 실무에서 어디에 쓰이나요?
A. 데이터베이스 인덱스 탐색, 정렬된 리스트에서 특정 값 찾기, 수치 해석에서 범위 좁히기 등 다양한 분야에서 활용됩니다.