이진 탐색

CS·데이터사이언스 고등 · v1 · 🤖 LLM 버전

정의

이진 탐색(binary search, 이분 탐색이라고도 한다)은 오름차순으로 정렬된 자료에서 특정한 값을 찾을 때, 탐색 범위를 매번 절반으로 줄여가며 원하는 값을 찾아내는 알고리즘이다.

배열 $a_1, a_2, \ldots, a_n$이 오름차순으로 정렬되어 있고 찾으려는 값이 $x$일 때, 알고리즘은 다음과 같이 진행된다.

1. 탐색 범위의 양 끝 인덱스를 $low = 1$, $high = n$으로 둔다.
2. 중앙 인덱스 $mid = \left\lfloor \dfrac{low+high}{2} \right\rfloor$($\lfloor \; \rfloor$는 바닥함수라 읽으며, 어떤 실수보다 크지 않은 최대의 정수를 뜻한다)를 계산한다.
3. $a_{mid}$와 $x$를 비교한다.
   • $a_{mid} = x$이면 탐색을 끝낸다.
   • $a_{mid} < x$이면 $low = mid+1$로 갱신한다.
   • $a_{mid} > x$이면 $high = mid-1$로 갱신한다.
4. $low > high$가 될 때까지 2~3을 반복한다. 이 경우 $x$는 배열에 존재하지 않는다.

직관

전화번호부나 사전에서 단어를 찾을 때 처음부터 한 장씩 넘기지 않고, 책의 가운데를 펼쳐 찾는 단어와 비교한 뒤 앞쪽인지 뒤쪽인지 판단해서 그 반쪽만 다시 살펴보는 방식과 같다. 한 번 비교할 때마다 살펴봐야 할 범위가 절반으로 줄어들기 때문에, 자료의 개수가 아무리 많아도 비교 횟수는 훨씬 느리게 늘어난다.

시간복잡도

크기가 $n$인 배열은 한 번 비교할 때마다 범위가 절반으로 줄어들므로, $n$을 계속 2로 나누어 1이 될 때까지 필요한 횟수, 즉 $\log_2 n$번 정도 비교하면 탐색이 끝난다. 따라서 이진 탐색의 시간복잡도는 $O(\log n)$(빅오 로그 엔이라 읽는다)이다. 이는 처음부터 순서대로 하나씩 비교하는 순차 탐색의 시간복잡도 $O(n)$보다 훨씬 빠르다. 예를 들어 원소가 100만 개여도 이진 탐색은 최대 약 20번의 비교로 탐색이 끝난다($2^{20} \approx 1048576$이기 때문).

예시

정렬된 수열 $2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91$ (인덱스 1~11)에서 $x=45$를 찾아보자.

• 1단계: $low=1, high=11$, $mid = \lfloor 6 \rfloor = 6$, $a_6 = 23 < 45$ → $low = 7$
• 2단계: $low=7, high=11$, $mid = \lfloor 9 \rfloor = 9$, $a_9 = 56 > 45$ → $high = 8$
• 3단계: $low=7, high=8$, $mid = \lfloor 7.5 \rfloor = 7$, $a_7 = 38 < 45$ → $low = 8$
• 4단계: $low=8, high=8$, $mid = 8$, $a_8 = 45 = x$ → 탐색 성공 (총 4번 비교)

비교 횟수가 배열 크기에 따라 얼마나 느리게 늘어나는지는 $\log_2 x$ 그래프로 확인할 수 있다.

🌍 실생활 예시

프로그래밍에서 버그가 처음 발생한 커밋을 찾을 때 쓰는 git bisect 명령어가 이진 탐색의 대표적인 활용이다. 수백 개의 커밋 이력 중 가운데 커밋을 확인해 버그가 있는지 없는지 판단하고, 그 결과에 따라 앞쪽 절반 또는 뒤쪽 절반만 다시 살펴보는 과정을 반복해서 원인이 되는 커밋을 빠르게 찾아낸다.

⚠️ 흔한 실수

• 잘못된 생각: 정렬되지 않은 자료에도 이진 탐색을 적용할 수 있다. → 왜 틀렸는가: 이진 탐색은 $a_{mid}$와 $x$의 대소 비교로 절반을 버리는 알고리즘인데, 자료가 정렬되어 있지 않으면 버린 절반에 실제로 $x$가 들어 있을 수 있어 잘못된 결과가 나온다.
• 잘못된 생각: 값을 못 찾았을 때 $low = mid$ 또는 $high = mid$로 갱신하면 된다. → 왜 틀렸는가: $mid$ 자체를 다시 범위에 포함시키면 $low$나 $high$가 줄어들지 않는 경우가 생겨 무한 반복에 빠질 수 있다. 반드시 $mid+1$, $mid-1$로 범위를 좁혀야 한다.
• 잘못된 생각: 반복 종료 조건을 $low < high$로 두어도 된다. → 왜 틀렸는가: $low = high$인 경우, 즉 범위에 원소가 하나 남은 경우를 검사하지 않고 종료해 버려 실제로는 존재하는 값을 못 찾고 실패로 판정하는 오류가 생긴다. 종료 조건은 $low > high$여야 한다.

확인 문제

1. 정렬된 수열 $3, 7, 10, 15, 22, 30, 41, 55$ (인덱스 1~8)에서 이진 탐색으로 $22$를 찾는 과정을 $low, high, mid$ 값과 함께 순서대로 적어보시오.
2. 크기가 1024인 정렬된 배열에서 이진 탐색으로 원하는 값을 찾으려면 최악의 경우 몇 번 비교해야 하는지 구하고, 왜 그런 횟수가 나오는지 설명하시오.
3. 정렬되지 않은 배열 $[7, 2, 9, 4, 1]$에서 $4$를 찾기 위해 이진 탐색의 절차(중앙값과 비교해서 절반을 버리는 방식)를 그대로 적용하면 어떤 문제가 생기는지 설명하시오.

관련 개념

• 수열 — 정렬된 배열을 다루는 이진 탐색의 기본 대상
• 부등식 — $a_{mid}$와 $x$의 대소를 비교해 범위를 좁히는 근거
• 시간복잡도 — 이진 탐색의 효율성을 $O(\log n)$으로 표현하는 척도
• 로그 — 이진 탐색의 비교 횟수가 $\log_2 n$에 비례하는 이유
• 재귀 알고리즘 — 이진 탐색을 재귀적으로 구현할 수도 있다