우리는 매일 수많은 정보의 홍수 속에서 살아갑니다. 이 거대한 데이터의 바다에서 원하는 특정 정보를 찾아내는 능력은 현대 사회를 살아가는 데 필수적인 기술이 되었습니다. 만약 당신 앞에 수백만 권의 책이 가나다순으로 정리된 거대한 도서관이 있고, 그중 단 한 권의 책을 찾아야 한다면 어떻게 하시겠습니까? 첫 번째 책부터 한 권씩 차례대로 확인하는 것은 상상만 해도 끔찍한 일일 겁니다. 아마 대부분의 사람들은 본능적으로 도서관의 중간쯤으로 가서 찾으려는 책의 제목이 현재 위치보다 앞에 있는지 뒤에 있는지 확인하고, 그에 따라 탐색할 범위를 절반으로 줄여나갈 것입니다. 바로 이 직관적인 탐색 방식이 컴퓨터 과학의 가장 근본적이고 강력한 알고리즘 중 하나인 이진 탐색(Binary Search)의 핵심 원리입니다.
이진 탐색은 단순히 '정렬된 배열에서 특정 값을 찾는 알고리즘'이라는 한 문장으로 정의되기에는 너무나도 깊고 넓은 의미를 담고 있습니다. 그것은 '분할 정복(Divide and Conquer)'이라는 위대한 문제 해결 전략의 정수를 보여주는 가장 대표적인 예시이며, 컴퓨터가 어떻게 인간의 직관적인 사고방식을 수학적 효율성으로 승화시키는지 명확하게 증명합니다. 이 글에서는 이진 탐색의 코드를 단순히 암기하는 것을 넘어, 그 속에 담긴 철학과 원리를 깊이 있게 파헤쳐 볼 것입니다. 왜 이진 탐색이 그토록 효율적인지, 그 효율성이 가지는 실질적인 의미는 무엇인지, 그리고 이 강력한 도구가 단순한 데이터 검색을 넘어 얼마나 다양한 문제들을 해결하는 데 사용될 수 있는지를 심도 있게 탐구해 나갈 것입니다.
이 글을 끝까지 읽고 나면, 여러분은 이진 탐색을 그저 하나의 검색 알고리즘으로 보는 것이 아니라, 복잡한 문제의 해답 공간을 효율적으로 줄여나가는 강력한 사고의 틀로 인식하게 될 것입니다. 이제, 정렬된 세상 속에서 가장 빠르게 답을 찾아가는 여정을 함께 시작하겠습니다.
1. 이진 탐색의 본질: 왜 반으로 나누는가?
이진 탐색의 마법은 '나눈다'는 행위에서 시작됩니다. 하지만 이 마법이 일어나기 위해서는 반드시 만족되어야 하는 절대적인 전제 조건이 있습니다. 바로 탐색의 대상이 되는 데이터 집합이 반드시 정렬(sorted)되어 있어야 한다는 것입니다. 이 조건이 왜 그토록 중요할까요? 데이터가 정렬되어 있다는 것은 그 안에 '순서'라는 정보가 내재되어 있음을 의미합니다. 이 순서 정보가 있기에 우리는 단 한 번의 비교만으로 앞으로 탐색할 필요가 없는 영역을 과감하게 버릴 수 있는 것입니다.
예를 들어, `[3, 5, 8, 12, 15, 18, 22, 27, 30, 34]` 라는 정렬된 배열에서 `27`이라는 값을 찾는 과정을 생각해 봅시다.
먼저 탐색 범위는 배열 전체입니다. 시작 인덱스(low)는 0, 끝 인덱스(high)는 9입니다.
low=0, high=9 [3, 5, 8, 12, 15, 18, 22, 27, 30, 34] ↑ ↑ ↑ low mid high
1단계: 첫 번째 비교
중간 인덱스(mid)를 계산합니다. `(0 + 9) / 2 = 4.5`이므로 정수 부분인 4를 취합니다. `mid = 4`입니다. 배열의 4번 인덱스에 있는 값은 `15`입니다. 우리가 찾으려는 값 `27`은 `15`보다 큽니다. 데이터가 오름차순으로 정렬되어 있다는 사실 때문에, 우리는 `15`를 포함한 그 이전의 모든 값들(`3, 5, 8, 12, 15`)은 절대 `27`이 될 수 없다는 확신을 가질 수 있습니다. 이 단 한 번의 비교로 탐색 범위의 절반 이상이 후보에서 제외됩니다. 이제 새로운 탐색 범위는 `mid + 1`인 5번 인덱스부터 기존의 끝 인덱스인 9번까지가 됩니다.
시각적으로 표현하면 다음과 같습니다.
탐색 대상: 27 mid 값: 15 (arr[4]) [3, 5, 8, 12, 15, | 18, 22, 27, 30, 34] ~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~ 버려지는 영역 새로운 탐색 영역 (low = mid + 1 = 5)
2단계: 두 번째 비교
이제 새로운 탐색 범위는 `low=5`, `high=9`입니다. 중간 인덱스는 `(5 + 9) / 2 = 7`입니다. 7번 인덱스의 값은 `27`입니다. 우리가 찾던 값과 정확히 일치합니다! 탐색은 성공적으로 종료됩니다.
low=5, high=9 [18, 22, 27, 30, 34] ↑ ↑ ↑ low mid high
만약 우리가 찾으려는 값이 `18`이었다면 어땠을까요? 2단계에서 `mid` 값인 `27`은 `18`보다 큽니다. 따라서 우리는 `27`을 포함한 그 이후의 모든 값들(`27, 30, 34`)은 답이 될 수 없다고 확신하고 버릴 수 있습니다. 새로운 탐색 범위는 `low=5`, `high=mid-1=6`이 됩니다.
이진 탐색의 진정한 힘은 값을 '찾는' 행위가 아니라, 가능성이 없는 수많은 후보군을 '버리는' 행위에 있습니다. 한 번의 비교가 끝날 때마다 탐색해야 할 범위가 절반으로 줄어드는 것, 이것이 이진 탐색이 경이로운 속도를 낼 수 있는 근본적인 이유입니다. 선형 탐색이 하나씩 확인하며 "이것이 답인가?"라고 묻는 방식이라면, 이진 탐색은 "답이 어느 쪽에 있는가?"라고 물으며 탐색의 공간 자체를 기하급수적으로 축소시키는 훨씬 더 지능적인 접근법입니다.
2. 효율성의 비밀: O(log n)의 경이로움
알고리즘의 성능을 평가할 때 우리는 '시간 복잡도(Time Complexity)'라는 척도를 사용합니다. 이는 데이터의 크기(n)가 증가함에 따라 연산 횟수가 얼마나 증가하는지를 나타냅니다. 이진 탐색의 시간 복잡도는 O(log n)입니다. 반면, 배열의 처음부터 끝까지 하나씩 비교하는 선형 탐색(Linear Search)의 시간 복잡도는 O(n)입니다.
이 차이가 현실에서 얼마나 큰 위력을 발휘하는지 숫자를 통해 체감해 봅시다.
| 데이터 개수 (n) | 선형 탐색 최악의 경우 (n번) | 이진 탐색 최악의 경우 (log₂n 번) |
|---|---|---|
| 1,024 (약 1천) | 1,024 번 | 10 번 |
| 1,048,576 (약 1백만) | 1,048,576 번 | 20 번 |
| 1,073,741,824 (약 10억) | 1,073,741,824 번 | 30 번 |
| 지구상 모든 사람 (약 80억) | 약 80억 번 | 약 33 번 |
표가 보여주는 결과는 충격적입니다. 데이터가 1천 개일 때만 해도 이진 탐색은 선형 탐색보다 100배 이상 빠릅니다. 데이터가 1백만 개로 늘어나면 그 차이는 5만 배 이상으로 벌어집니다. 10억 개의 데이터 속에서 값을 찾는 데 단 30번의 비교만으로 충분하다는 것은 거의 마법에 가깝습니다. 만약 전 세계 80억 명의 사람을 나이순으로 정렬한 뒤 특정인을 찾는다고 해도, 이진 탐색은 단 33~34번의 비교만으로 그 사람을 찾아낼 수 있습니다. 선형 탐색으로는 최악의 경우 80억 번의 비교가 필요합니다.
여기서 `log n`의 진정한 의미는 "n을 1이 될 때까지 몇 번이나 2로 나눌 수 있는가?"입니다. 이는 탐색 범위를 절반으로 줄여나가는 이진 탐색의 과정과 완벽하게 일치합니다. 데이터의 양이 2배로 늘어나도, 이진 탐색에 필요한 연산은 고작 1번만 추가될 뿐입니다. 이러한 '로그 스케일'의 효율성 덕분에 이진 탐색은 빅데이터 시대에 더욱 빛을 발하는 알고리즘이 되었습니다.
일상 생활에서 O(log n)의 위력을 느낄 수 있는 좋은 예는 '스무고개' 게임입니다. 누군가 세상에 있는 사물 중 하나를 생각하고, 우리는 스무 번의 '예/아니오' 질문으로 그것을 맞춰야 합니다. 유능한 질문자는 "살아있는 것입니까?"와 같이 한 번의 질문으로 가능한 답의 범위를 절반 가까이 줄여나갑니다. 이것이 바로 이진 탐색의 전략입니다. 스무 번의 질문으로 정답을 맞힐 수 있다는 것은, 2의 20제곱, 즉 약 1백만 개의 보기 중에서 정답을 찾아낼 수 있다는 의미와 같습니다. 이진 탐색은 컴퓨터가 우리와 스무고개 게임을 하는 것과 같습니다. 다만, 훨씬 더 빠르고 정확하게 할 뿐입니다.
3. 구현의 두 얼굴: 반복문과 재귀
이진 탐색 알고리즘은 크게 두 가지 방식으로 구현할 수 있습니다: 반복문(Iteration)을 사용하는 방식과 재귀(Recursion)를 사용하는 방식입니다. 두 방식은 동일한 원리를 기반으로 하지만, 코드의 구조와 실행 방식, 그리고 성능 특성에서 미묘한 차이를 보입니다. 각각의 장단점을 이해하는 것은 상황에 맞는 최적의 코드를 작성하는 데 중요합니다.
3.1. 반복문(Iterative) 방식
반복문 방식은 `while` 루프를 사용하여 탐색 범위(`low`와 `high`)를 계속해서 갱신해나가는, 가장 직관적이고 일반적인 구현법입니다. 루프는 `low`가 `high`보다 커지기 전까지, 즉 탐색할 범위가 남아있는 동안 계속됩니다.
다음은 Python으로 작성된 반복문 방식의 이진 탐색 코드입니다.
def binary_search_iterative(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
# mid = (low + high) // 2 # 이 방식은 오버플로우 가능성이 있음
mid = low + (high - low) // 2 # 오버플로우를 방지하는 더 안전한 방식
if arr[mid] == target:
return mid # 값을 찾았을 경우 인덱스 반환
elif arr[mid] < target:
low = mid + 1 # 중간값이 타겟보다 작으면, 오른쪽 부분을 탐색
else:
high = mid - 1 # 중간값이 타겟보다 크면, 왼쪽 부분을 탐색
return -1 # 값을 찾지 못했을 경우 -1 반환
코드 해설:
- `low`와 `high`는 현재 탐색하고 있는 배열의 부분(subarray)의 시작과 끝 인덱스를 가리킵니다.
- `while low <= high:`: 이 조건은 탐색할 원소가 하나라도 남아있는지를 확인합니다. 만약 `low`가 `high`보다 커지면, 이는 탐색 범위가 비어있음을 의미하며, 배열에 찾는 값이 없다는 뜻입니다.
- `mid = low + (high - low) // 2`: 중간 인덱스를 계산합니다. `(low + high) // 2`는 `low`와 `high`의 값이 매우 클 경우 정수 오버플로우(integer overflow)를 일으킬 수 있습니다. C++, Java와 같이 정수 타입의 최대값이 정해진 언어에서는 특히 중요합니다. `low + (high - low) // 2`는 수학적으로 동일한 결과를 내면서도 오버플로우의 위험이 없어 더 안전한 방법으로 권장됩니다.
- 분기 처리: `arr[mid]`의 값을 `target`과 비교하여 `low` 또는 `high` 값을 갱신함으로써 탐색 범위를 절반으로 줄입니다. `arr[mid]`를 이미 확인했으므로, 다음 탐색 범위는 `mid`를 제외한 `mid + 1` 또는 `mid - 1`부터 시작하는 것이 핵심입니다.
장점:
- 메모리 효율성: 추가적인 함수 호출이 없으므로 콜 스택(call stack)에 메모리가 쌓이지 않습니다. 따라서 데이터 크기에 상관없이 일정한 메모리만 사용합니다 (O(1) 공간 복잡도).
- 속도: 함수 호출에 따르는 오버헤드가 없기 때문에, 일반적으로 재귀 방식보다 미세하게 더 빠릅니다.
3.2. 재귀(Recursive) 방식
재귀 방식은 문제를 더 작은 동일한 문제로 나누어 해결하는 '분할 정복'의 철학을 코드에 그대로 반영합니다. 이진 탐색 함수가 자기 자신을 다시 호출하여 좁혀진 탐색 범위에 대해 동일한 작업을 반복합니다.
다음은 Python으로 작성된 재귀 방식의 이진 탐색 코드입니다.
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1 # 기저 조건(Base case): 탐색 실패
mid = low + (high - low) // 2
if arr[mid] == target:
return mid # 기저 조건(Base case): 탐색 성공
elif arr[mid] < target:
# 오른쪽 부분을 재귀적으로 탐색
return binary_search_recursive(arr, target, mid + 1, high)
else:
# 왼쪽 부분을 재귀적으로 탐색
return binary_search_recursive(arr, target, low, mid - 1)
# 사용 예시
# arr = [3, 5, 8, 12, 15, 18, 22, 27, 30, 34]
# target = 27
# result = binary_search_recursive(arr, target, 0, len(arr) - 1)
코드 해설:
- 기저 조건(Base Case): 재귀 함수에서 가장 중요한 부분입니다. 무한 루프에 빠지지 않도록 재귀를 멈추는 조건입니다. 이진 탐색에서는 1) 값을 찾았을 때 (`arr[mid] == target`)와 2) 더 이상 탐색할 범위가 없을 때 (`low > high`)가 기저 조건이 됩니다.
- 재귀 호출: `arr[mid]`와 `target`을 비교한 결과에 따라, 다음 탐색 범위(`low`, `high`)를 인자로 하여 자기 자신을 다시 호출합니다. `return` 키워드를 통해 재귀 호출의 최종 결과를 상위 호출로 전달하는 것이 중요합니다.
장점:
- 가독성: 코드가 알고리즘의 '분할 정복' 논리를 그대로 따르기 때문에, 일부 개발자에게는 더 직관적이고 이해하기 쉽게 느껴질 수 있습니다.
- 간결함: 문제의 정의를 코드로 표현하기에 용이하여 코드가 더 간결해질 수 있습니다.
단점:
- 메모리 사용량: 함수가 호출될 때마다 콜 스택에 메모리(매개변수, 복귀 주소 등)가 쌓입니다. 탐색의 깊이, 즉 `log n`에 비례하는 공간 복잡도(O(log n))를 가집니다. 데이터의 양이 극단적으로 많으면 스택 오버플로우(stack overflow)가 발생할 가능성이 이론적으로 존재합니다.
반복문 vs 재귀: 무엇을 선택할 것인가?
대부분의 실용적인 상황, 특히 성능이 중요한 경쟁 프로그래밍이나 시스템 레벨의 코딩에서는 반복문 방식이 선호됩니다. 미세한 속도 이점과 스택 오버플로우의 위험이 없다는 안정성 때문입니다. 하지만 재귀 방식은 알고리즘의 원리를 교육적으로 설명하거나, 후술할 트리(Tree) 자료구조와 같이 재귀적 정의가 자연스러운 문제를 다룰 때 매우 유용하고 우아한 해결책이 될 수 있습니다. 두 가지 방식을 모두 이해하고 자유자재로 변환할 수 있는 능력은 개발자의 문제 해결 능력을 한 단계 끌어올려 줄 것입니다.
4. 이진 탐색의 전제 조건과 그 너머
앞서 강조했듯이 이진 탐색의 가장 중요한 전제 조건은 '정렬'입니다. 만약 데이터가 정렬되어 있지 않다면, 중간 값을 확인하더라도 나머지 절반을 버릴 수 있는 논리적 근거가 사라지기 때문에 이진 탐색은 완전히 무용지물이 됩니다. 그렇다면 데이터를 탐색하기 전에 항상 정렬을 먼저 해야 할까요? 이 질문은 중요한 트레이드오프(trade-off)를 시사합니다.
4.1. 정렬의 비용
효율적인 정렬 알고리즘(예: 병합 정렬, 퀵 정렬)의 시간 복잡도는 일반적으로 O(n log n)입니다. 이는 O(n)인 선형 탐색이나 O(log n)인 이진 탐색보다 훨씬 더 많은 연산을 필요로 합니다.
- 단 한 번의 검색: 만약 정렬되지 않은 데이터에서 단 한 번만 값을 찾을 거라면, O(n log n)의 비용을 들여 정렬한 뒤 O(log n)으로 탐색하는 것보다 그냥 O(n)의 선형 탐색을 하는 것이 훨씬 효율적입니다. `(O(n log n) + O(log n)) > O(n)` 이기 때문입니다.
- 여러 번의 검색: 하지만 동일한 데이터에 대해 여러 번(k번)의 검색 요청이 있다면 이야기가 달라집니다. 정렬을 한 번 해두면, 총비용은 `O(n log n) + k * O(log n)`이 됩니다. 정렬 없이 매번 선형 탐색을 한다면 총비용은 `k * O(n)`입니다. 검색 횟수 `k`가 충분히 커지면, 초기에 정렬 비용을 지불하더라도 장기적으로는 이진 탐색을 사용하는 것이 압도적으로 유리해집니다.
결론적으로, 데이터가 자주 변경되지 않고 검색이 빈번하게 일어나는 시스템(예: 데이터베이스 인덱스, 사전 검색)에서 이진 탐색의 가치는 극대화됩니다.
4.2. 이진 탐색의 확장: 파라메트릭 서치(Parametric Search)
이진 탐색의 진정한 힘은 정렬된 '배열'에서 값을 찾는 것을 넘어, '답의 후보가 되는 연속적인 범위' 내에서 최적의 해를 찾는 문제로 확장될 때 드러납니다. 이를 파라메트릭 서치라고 부릅니다.
파라메트릭 서치는 다음과 같은 구조를 가진 문제에 적용할 수 있습니다.
- 우리가 찾으려는 답(예: 최소 시간, 최대 거리 등)이 특정 범위 `[min_val, max_val]` 안에 있다는 것을 알고 있습니다.
- 어떤 임의의 값 `x`에 대해, "정답이 `x`가 될 수 있는가?" (또는 `x`보다 크거나 같은가?, `x`보다 작거나 같은가?)를 판별할 수 있는 함수(결정 함수, decision function)를 만들 수 있습니다.
- 이 결정 함수의 결과는 `x`에 대해 단조성(monotonicity)을 가집니다. 즉, 어떤 `x`에 대해 'YES'가 나왔다면, 그보다 더 완화된 조건(예: `x`보다 작은 값)에 대해서도 항상 'YES'가 나오거나, 그 반대의 관계가 성립해야 합니다.
이 세 가지 조건이 만족되면, 우리는 정답의 범위를 대상으로 이진 탐색을 수행할 수 있습니다. `low`를 `min_val`, `high`를 `max_val`로 설정하고, `mid` 값을 결정 함수에 넣어 그 결과에 따라 `low`나 `high`를 조절하며 최적의 해를 찾아가는 것입니다.
예시 문제: 떡볶이 떡 자르기 (백준 1927번)
문제: 길이가 제각각인 떡들이 일렬로 놓여 있습니다. 절단기에 높이(H)를 지정하면, 그 높이보다 긴 떡들은 H 위의 부분이 잘리고, 낮은 떡들은 잘리지 않습니다. 이렇게 잘린 떡들의 길이의 총합이 최소한 M만큼이 되도록 하는 절단기의 최대 높이(H)를 구하는 문제입니다.
이 문제를 어떻게 파라메트릭 서치로 해결할 수 있을까요?
- 답의 범위: 절단기의 높이(H)는 0부터 가장 긴 떡의 길이 사이의 값일 것입니다. 이 범위를 `[low, high]`로 설정합니다.
- 결정 함수: `check(H)` 라는 함수를 만듭니다. 이 함수는 "절단기 높이를 H로 설정했을 때, 잘린 떡의 총합이 M 이상인가?"를 판별하여 `True` 또는 `False`를 반환합니다. 이 함수는 모든 떡을 한 번씩 순회하며 계산할 수 있으므로 O(n)의 시간이 걸립니다.
- 단조성: 만약 높이 `H`에서 M 이상의 떡을 얻었다면(`check(H) == True`), 그보다 낮은 높이 `H-1`에서는 당연히 더 많은 떡을 얻을 수 있으므로 항상 `check(H-1) == True`가 성립합니다. 반대로 `H`에서 M 이상의 떡을 얻지 못했다면(`check(H) == False`), 더 높은 높이 `H+1`에서는 더 적은 떡을 얻게 되므로 항상 `check(H+1) == False`가 됩니다. 이러한 단조성이 존재하므로 이진 탐색을 적용할 수 있습니다.
해결 과정:
- `low = 0`, `high = max(떡들의 길이)`로 설정합니다.
- `while low <= high:` 루프를 실행합니다.
- `mid = (low + high) // 2`를 계산합니다.
- `check(mid)`를 호출합니다.
- 결과가 `True` (M 이상 획득 가능)이면, `mid`는 정답 후보가 될 수 있습니다. 더 높은 높이도 가능한지 알아보기 위해 `result = mid`, `low = mid + 1`로 범위를 좁힙니다.
- 결과가 `False` (M 이상 획득 불가)이면, `mid`는 너무 높은 높이입니다. 높이를 낮춰야 하므로 `high = mid - 1`로 범위를 좁힙니다.
- 루프가 끝나면 `result`에 저장된 값이 최적의 해가 됩니다.
이처럼 파라메트릭 서치는 이진 탐색의 원리를 '답의 공간'으로 확장하여, 직접적인 해결이 어려운 최적화 문제를 효율적인 결정 문제로 변환하여 해결하는 매우 강력한 기법입니다. 이는 이진 탐색이 단순한 검색 알고리즘을 넘어선 고급 문제 해결 패러다임임을 보여주는 대표적인 사례입니다.
5. 변형된 이진 탐색: 경계를 찾는 기술
지금까지 다룬 표준적인 이진 탐색은 배열에 특정 값이 '존재하는지' 여부와 그 '위치'를 찾는 데 초점을 맞췄습니다. 하지만 실전에서는 데이터에 중복된 값이 존재할 때, 특정 값의 시작 위치나 끝 위치를 찾아야 하는 경우가 더 많습니다. 예를 들어, `[2, 5, 5, 5, 8, 10, 12]` 배열에서 `5`를 찾을 때, 표준 이진 탐색은 세 개의 `5` 중 어떤 것의 인덱스를 반환할지 보장하지 않습니다. 이러한 문제를 해결하기 위해 이진 탐색을 약간 변형한 Lower Bound와 Upper Bound 개념이 등장합니다.
5.1. Lower Bound (하한)
Lower Bound는 '찾으려는 값(target) 이상이 처음으로 나타나는 위치'를 찾는 알고리즘입니다. 만약 배열에 target 값이 존재한다면, 그 값들 중 가장 첫 번째 값의 인덱스를 반환합니다. 만약 target 값이 존재하지 않는다면, target보다 큰 값 중에서 가장 먼저 나타나는 값의 인덱스를 반환합니다.
표준 이진 탐색과의 핵심적인 차이는 `arr[mid] == target`일 때의 처리 방식에 있습니다.
def lower_bound(arr, target):
low = 0
high = len(arr)
ans = len(arr) # 만약 target 이상인 값이 없으면, 배열의 끝을 가리키도록 초기화
while low < high:
mid = low + (high - low) // 2
if arr[mid] >= target:
# mid가 target 이상이므로, mid는 후보가 될 수 있음
# 더 앞쪽에 target 이상인 값이 있는지 확인하기 위해 범위를 왼쪽으로 좁힘
ans = mid
high = mid
else:
# mid가 target보다 작으므로, mid와 그 왼쪽은 절대 답이 될 수 없음
low = mid + 1
return ans
로직 분석:
- `arr[mid] >= target`: `mid` 위치의 값이 `target`보다 크거나 같으면, `mid`는 일단 정답 후보가 됩니다. 하지만 우리는 '처음으로' 나타나는 위치를 찾고 있으므로, `mid`보다 더 왼쪽에 같은 값이 있을 가능성을 배제할 수 없습니다. 따라서 현재 찾은 `ans = mid`를 기록해두고, 탐색 범위를 왼쪽으로 좁힙니다(`high = mid`).
- `arr[mid] < target`: `mid` 위치의 값이 `target`보다 작으면, `mid`를 포함한 왼쪽 부분은 절대 답이 될 수 없습니다. 따라서 탐색 범위를 오른쪽으로 좁힙니다(`low = mid + 1`).
5.2. Upper Bound (상한)
Upper Bound는 '찾으려는 값(target)을 초과하는 값이 처음으로 나타나는 위치'를 찾는 알고리즘입니다.
def upper_bound(arr, target):
low = 0
high = len(arr)
ans = len(arr)
while low < high:
mid = low + (high - low) // 2
if arr[mid] > target:
# mid가 target을 초과하므로, mid는 후보가 될 수 있음
# 더 앞쪽에 target을 초과하는 값이 있는지 확인하기 위해 범위를 왼쪽으로 좁힘
ans = mid
high = mid
else:
# mid가 target 이하이므로, mid와 그 왼쪽은 절대 답이 될 수 없음
low = mid + 1
return ans
로직 분석:
- `arr[mid] > target`: `mid` 위치의 값이 `target`보다 크면, `mid`는 정답 후보입니다. 더 좋은 답(더 왼쪽)을 찾기 위해 `ans = mid`를 기록하고 `high = mid`로 범위를 좁힙니다.
- `arr[mid] <= target`: `mid` 위치의 값이 `target`보다 작거나 같으면, `mid`를 포함한 왼쪽 부분은 절대 답이 될 수 없습니다. 따라서 `low = mid + 1`로 범위를 좁힙니다.
5.3. Lower Bound와 Upper Bound의 활용
이 두 가지 변형된 이진 탐색을 조합하면 매우 유용한 정보를 얻을 수 있습니다. 예를 들어, 정렬된 배열에서 특정 값 `target`의 개수를 세고 싶다면 어떻게 해야 할까요?
정답은 `upper_bound(target) - lower_bound(target)` 입니다.
`lower_bound(target)`는 `target`이 시작되는 첫 번째 인덱스를 알려주고, `upper_bound(target)`는 `target`의 마지막 위치 바로 다음 인덱스(즉, `target`보다 큰 첫 번째 값의 인덱스)를 알려주기 때문입니다. 두 인덱스의 차이가 바로 배열 내 `target`의 개수가 됩니다.
예시: `arr = [2, 5, 5, 5, 8, 10, 12]`, `target = 5`
- `lower_bound(arr, 5)`는 인덱스 `1`을 반환합니다.
- `upper_bound(arr, 5)`는 인덱스 `4`를 반환합니다.
- `5`의 개수 = `4 - 1 = 3`개 입니다.
이처럼 Lower Bound와 Upper Bound는 단순한 존재 유무를 넘어 데이터의 분포와 관련된 더 정교한 질문에 답할 수 있게 해주는 이진 탐색의 강력한 확장 기술입니다.
6. 현실 세계의 이진 탐색: 어디에 숨어 있을까?
이진 탐색은 단순히 알고리즘 경진대회나 기술 면접에만 등장하는 이론적인 개념이 아닙니다. 우리는 이미 일상 속에서 이진 탐색의 원리로 동작하는 수많은 기술의 혜택을 누리고 있습니다.
- 데이터베이스 인덱싱: 대용량 데이터베이스는 빠른 검색을 위해 특정 컬럼을 기준으로 인덱스(Index)를 생성합니다. B-Tree와 같은 인덱스 자료구조는 내부적으로 데이터가 정렬된 상태로 유지되며, 특정 레코드를 찾는 과정은 이진 탐색과 매우 유사한 원리로 동작하여 수억 개의 데이터 속에서도 눈 깜짝할 사이에 원하는 정보를 찾아냅니다.
- Git Bisect: 버전 관리 시스템 Git에는 버그를 유발한 커밋(commit)을 찾는 `git bisect`라는 강력한 명령어가 있습니다. 이 명령어는 전체 커밋 히스토리(시간순으로 정렬된)를 대상으로 이진 탐색을 수행합니다. 개발자는 중간 지점의 커밋을 테스트하여 버그 유무를 알려주기만 하면, Git은 자동으로 문제의 범위를 절반으로 줄여나가며, 최종적으로 버그를 최초로 발생시킨 단 하나의 커밋을 정확히 찾아내 줍니다. 수천 개의 커밋 속에서 버그 원인을 찾는 끔찍한 디버깅 과정을 O(log n)의 효율성으로 해결해 주는 놀라운 도구입니다.
- 사전 및 자동 완성: 우리가 사용하는 사전 앱이나 검색 엔진의 자동 완성 기능은 내부적으로 정렬된 단어 목록을 가지고 있습니다. 사용자가 단어를 입력하기 시작하면, 이진 탐색(또는 트라이(Trie)와 같은 더 특화된 자료구조)을 사용하여 가능한 후보 단어 목록을 매우 빠르게 찾아 제시합니다.
- 수치 해석 (Numerical Analysis): 어떤 함수의 해(root)를 찾는 문제, 예를 들어 `f(x) = 0`을 만족하는 `x`를 찾는 문제에서도 이진 탐색과 유사한 '이분법(Bisection method)'이 사용됩니다. 함수값이 양수인 지점과 음수인 지점을 찾은 뒤, 그 사이의 중간 지점을 계속해서 탐색하며 해의 범위를 좁혀나가는 방식입니다.
- 라우터의 라우팅 테이블: 인터넷 공유기(라우터)는 IP 주소에 따라 데이터를 어디로 보낼지 결정하는 라우팅 테이블을 가지고 있습니다. 이 테이블은 네트워크 주소에 따라 정렬되어 있으며, 특정 IP 패킷이 들어왔을 때 가장 적합한 경로를 찾기 위해 이진 탐색과 유사한 빠른 검색 알고리즘이 사용됩니다.
이처럼 이진 탐색은 컴퓨터 과학의 근간을 이루는 핵심 아이디어로서, 우리가 직접 인지하지 못하는 수많은 곳에서 시스템의 효율성을 책임지고 있는 숨은 영웅과도 같습니다.
7. 흔히 저지르는 실수와 디버깅 팁
이진 탐색은 원리는 간단하지만, 막상 직접 구현하다 보면 사소한 실수로 인해 무한 루프에 빠지거나 잘못된 결과를 내기 쉬운, 의외로 까다로운 알고리즘입니다. 다음은 개발자들이 흔히 저지르는 실수와 그 해결책입니다.
- Off-by-one 오류 (경계 값 설정 오류):
- 루프 조건: `while (low < high)`로 할지, `while (low <= high)`로 할지 혼동하는 경우가 많습니다.
- `low <= high`: 이 방식은 탐색 범위에 원소가 하나 남은 경우(`low == high`)까지도 루프가 실행되도록 합니다. 일반적으로 값을 정확히 찾는 표준 이진 탐색에 더 직관적이고 안전합니다.
- `low < high`: 이 방식은 `low`와 `high`가 같아지는 순간 루프가 종료됩니다. Lower/Upper bound 구현 시 종료 조건을 다루기 위해 사용되기도 하지만, 정확한 이해 없이 사용하면 마지막 원소를 검사하지 못하는 실수를 유발할 수 있습니다.
- 포인터 업데이트: `high = mid`로 할지, `high = mid - 1`로 할지 결정하는 것이 중요합니다. `arr[mid]`를 이미 확인했다면, 다음 탐색 범위에서는 `mid`를 제외해야 합니다. 따라서 `high = mid - 1`과 `low = mid + 1`이 표준적인 업데이트 방식입니다. 이 규칙을 어기면 특정 조건에서 `low`나 `high`가 변하지 않아 무한 루프에 빠질 수 있습니다.
- 루프 조건: `while (low < high)`로 할지, `while (low <= high)`로 할지 혼동하는 경우가 많습니다.
- 정수 오버플로우 (Integer Overflow):
- 앞서 언급했듯이 `mid = (low + high) / 2`는 `low`와 `high`가 매우 클 때 두 합이 정수 타입의 표현 범위를 넘어설 수 있습니다. Python은 임의 정밀도 정수를 지원하여 이 문제에서 자유롭지만, C++, Java, C# 등에서는 심각한 버그를 유발합니다. 항상 `mid = low + (high - low) / 2`를 사용하는 습관을 들이는 것이 좋습니다.
- 재귀 구현 시 `return` 누락:
- 재귀 함수에서 자기 자신을 호출할 때, 그 호출의 결과를 `return`하는 것을 잊는 경우가 많습니다. `binary_search_recursive(...)`와 같이 호출만 하고 반환하지 않으면, 값을 찾더라도 그 결과가 상위 호출 스택으로 전달되지 않아 최종적으로는 `None`이나 쓰레기 값이 반환될 수 있습니다. 반드시 `return binary_search_recursive(...)` 형태로 작성해야 합니다.
이진 탐색 코드를 디버깅할 때는 각 단계마다 `low`, `high`, `mid` 변수의 값을 출력해보는 것이 매우 효과적입니다. 탐색 범위가 예상대로 줄어들고 있는지, 무한 루프의 징후는 없는지를 눈으로 직접 확인하면 문제의 원인을 빠르게 파악할 수 있습니다.
결론: 사고의 틀로서의 이진 탐색
이진 탐색은 정렬된 배열에서 데이터를 효율적으로 검색하는 하나의 알고리즘 그 이상입니다. 그것은 복잡하고 방대한 문제 공간을 마주했을 때, 어떻게 하면 가장 효율적으로 해답에 접근할 수 있는지에 대한 근본적인 통찰을 제공하는 강력한 '사고의 틀'입니다.
'분할 정복'의 정수를 보여주는 이진 탐색은 우리에게 가르칩니다. 해결 불가능해 보이는 거대한 문제도, 논리적인 기준에 따라 더 작은 문제로 나눌 수만 있다면 결국 해결할 수 있다는 것을 말입니다. 그리고 그 과정에서 불필요한 가능성들을 과감하게 제거하는 것이 핵심이라는 사실을 일깨워줍니다. O(log n)이라는 경이로운 시간 복잡도는 이러한 접근법이 얼마나 폭발적인 효율성을 가져오는지 수학적으로 증명합니다.
파라메트릭 서치를 통해 우리는 이진 탐색의 원리가 단순히 데이터의 배열을 넘어, 추상적인 '해답의 공간'에도 적용될 수 있음을 확인했습니다. Lower/Upper Bound는 중복 데이터가 존재하는 현실 세계의 문제들을 더 정교하게 다룰 수 있는 도구를 제공했습니다.
이제 여러분이 어떤 문제에 부딪혔을 때, 다음과 같은 질문을 스스로에게 던져보십시오. "이 문제의 답은 어떤 연속적인 범위를 가지는가?", "그 범위 내의 어떤 값에 대해 'YES/NO'로 판별할 수 있는 기준이 있는가?", "그 판별 기준은 단조성을 가지는가?" 만약 이 질문들에 긍정적인 답을 할 수 있다면, 여러분은 이진 탐색이라는 강력한 무기를 사용할 수 있습니다.
이진 탐색을 깊이 이해한다는 것은 단순히 코드 한 조각을 외우는 것이 아닙니다. 그것은 세상을 바라보고 문제를 해결하는 새로운 관점을 얻는 것과 같습니다. 정렬된 세상 속에서 가장 빠르게 답을 찾는 지혜, 그것이 바로 이진 탐색이 우리에게 주는 가장 큰 선물일 것입니다.