# 이진 탐색 분야: CS·데이터사이언스 학교급: 고등 정식 URL: https://pi.devxdev.xyz/wiki/math/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89 --- ## 정의 이진 탐색(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$ 그래프로 확인할 수 있다. 그래프: y=log2(x) (정의역 1~1024) ## 🌍 실생활 예시 프로그래밍에서 버그가 처음 발생한 커밋을 찾을 때 쓰는 `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$를 찾기 위해 이진 탐색의 절차(중앙값과 비교해서 절반을 버리는 방식)를 그대로 적용하면 어떤 문제가 생기는지 설명하시오. 정답 보기: 1. $low=1, high=8$, $mid=4$, $a_4=15<22$ → $low=5$. $low=5, high=8$, $mid=6$, $a_6=30>22$ → $high=5$. $low=5, high=5$, $mid=5$, $a_5=22=x$ → 성공 (3번 비교). 2. 최대 10번 비교한다. $1024 = 2^{10}$이므로, 범위를 절반으로 줄이는 과정을 10번 반복하면 남은 원소가 1개가 되기 때문이다($1024 \to 512 \to 256 \to \cdots \to 1$). 3. 배열이 정렬되어 있지 않으므로 중앙값 $9$와 $4$를 비교해 $4$가 더 작다고 왼쪽 절반 $[7, 2]$만 남기고 오른쪽 $[4, 1]$을 버리면, 실제로 $4$가 들어 있는 부분을 버리게 되어 값을 찾지 못한다. ## 관련 개념 - 수열 — 정렬된 배열을 다루는 이진 탐색의 기본 대상 - 부등식 — $a_{mid}$와 $x$의 대소를 비교해 범위를 좁히는 근거 - 시간복잡도 — 이진 탐색의 효율성을 $O(\log n)$으로 표현하는 척도 - 로그 — 이진 탐색의 비교 횟수가 $\log_2 n$에 비례하는 이유 - 재귀 알고리즘 — 이진 탐색을 재귀적으로 구현할 수도 있다 --- 관련 개념: - 수열 (/wiki/math/%EC%88%98%EC%97%B4) - 부등식 (/wiki/math/%EB%B6%80%EB%93%B1%EC%8B%9D) - 시간복잡도 (/wiki/math/%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84) - 로그 (/wiki/math/%EB%A1%9C%EA%B7%B8) - 재귀 알고리즘 (/wiki/math/%EC%9E%AC%EA%B7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)