이분탐색(binary search)은 정렬된 배열에서 숫자 하나를 찾는 알고리즘으로만 외우기 쉽습니다. 하지만 실전에서는 lower bound, upper bound, first true, parametric search까지 이어지는 경계 탐색의 사고법으로 훨씬 더 자주 쓰입니다.
이번 글은 이분 탐색을 공식 암기가 아니라 조건이 바뀌는 지점을 찾아 한쪽 절반을 버리는 방식으로 다시 설명합니다. 직관을 먼저 잡고, 그다음에 코드로 내려가겠습니다.
핵심 감각
많은 입문자는 이분 탐색을 가운데 값을 보고 왼쪽이나 오른쪽으로 가는 알고리즘으로 기억합니다. 틀린 말은 아니지만, 이 설명만으로는 응용이 잘 이어지지 않습니다.
진짜 핵심은 mid를 기준으로 어느 절반 전체를 버려도 되는가입니다. 중간값 자체보다 더 중요한 것은 경계가 어디서 바뀌는가입니다.
값 찾기
가장 익숙한 형태는 정렬된 배열에서 특정 값의 존재 여부를 찾는 문제입니다. 예를 들어 [1, 3, 5, 7, 9, 11, 13]에서 7을 찾는 경우입니다.
이 경우에는 arr[mid] == target인지가 핵심입니다. 만약 찾는 값이 8이라면, 7보다 큰 값만 오른쪽에 있으므로 왼쪽 절반은 통째로 버릴 수 있습니다. 바로 이 절반 버리기가 이분 탐색의 본질입니다.
경계 보기
배열이 [1, 2, 4, 4, 4, 7, 9]라고 해보겠습니다. 여기서 4를 찾는 것보다 더 자주 나오는 질문은 첫 번째 4의 위치, 4보다 큰 값이 처음 나오는 위치, 7 이상이 처음 나오는 위치 같은 것들입니다.
이 순간부터는 exact match보다 경계가 더 중요해집니다. 같은 값이 여러 개 있을 때는 찾았다는 사실만으로는 정보가 부족하기 때문입니다.
로어 바운드
lower bound는 보통 target 이상이 처음 나오는 위치라고 이해하면 편합니다. 같은 배열에서 lower_bound(4)는 첫 번째 4의 위치입니다.
이 위치를 기준으로 보면 왼쪽은 모두 4 미만이고, 오른쪽은 모두 4 이상입니다. 즉 lower bound는 작다와 이상이다의 경계입니다.
Python 공식 문서도 bisect_left를 값을 찾는 함수보다 삽입 위치를 찾는 함수로 설명합니다. 이 관점을 잡으면 경계 탐색이 훨씬 자연스러워집니다.
어퍼 바운드
upper bound는 보통 target보다 큰 값이 처음 나오는 위치입니다. 같은 배열에서 upper_bound(4)는 7이 있는 위치가 됩니다.
이제 왼쪽 구간은 모두 4 이하, 오른쪽 구간은 모두 4 초과가 됩니다. 즉 upper bound는 이하와 초과의 경계입니다.
lower bound와 upper bound는 값을 찾는 함수라기보다, 조건이 처음 만족되거나 처음 깨지는 지점을 찾는 함수입니다.
왜 자주 쓰일까
정렬 배열에서 특정 값의 개수, 처음 조건을 만족하는 원소, 중복 값 구간 길이 같은 문제는 exact match 하나만으로는 매끄럽게 풀리지 않습니다. 이럴 때는 경계 두 개를 찾는 쪽이 더 일반적입니다.
예를 들어 어떤 값 x의 등장 횟수는 upper_bound(x) - lower_bound(x)처럼 매우 자연스럽게 계산할 수 있습니다.
배열 밖으로
이제 질문을 바꿔보겠습니다. 정렬된 배열에서 인덱스를 찾는 게 아니라, 답이 될 수 있는 값 자체를 찾는다면 어떨까요?
예를 들어 최소 처리 속도, 최소 예산 상한선, 최소 블루레이 크기처럼 값 하나를 정했을 때 가능한지 불가능한지를 판별할 수 있는 문제들이 있습니다. 이 경우에도 가능한 값과 불가능한 값 사이에 경계가 한 번만 바뀌면 이분 탐색이 됩니다.
첫 true 찾기
answer search는 lower bound의 발상을 배열 인덱스가 아니라 답의 범위에 적용한 것에 가깝습니다. 어떤 속도 x가 주어졌을 때 작업을 제한 시간 안에 끝낼 수 있는지 판별한다고 해보겠습니다.
속도가 너무 느리면 불가능하고, 충분히 빠르면 가능할 것입니다. 그러면 속도 축은 false false false true true true처럼 보일 수 있습니다. 이때 찾고 싶은 것은 처음으로 true가 되는 값입니다.
배열이 없어도, 이 구조는 false와 true의 경계를 찾는 lower bound처럼 이해할 수 있습니다.
파라메트릭 서치
코딩테스트 맥락에서 parametric search는 보통 답 후보를 하나 정한 뒤, 그 값이 가능한지 판별하는 함수를 만들고, 그 판별 결과의 단조성을 이용해 이분 탐색하는 방식을 말합니다.
여기서 중요한 것은 이름보다 구조입니다. 판별 결과가 false false false true true true 또는 true true true false false false처럼 한 번만 바뀌어야 한쪽 절반 전체를 버릴 수 있습니다.
그래서 lower bound와 parametric search를 따로 외우기보다 같은 경계 탐색 축으로 묶어 이해하는 편이 훨씬 강력합니다.
코드 패턴
먼저 Python으로 패턴을 짧게 잡아보겠습니다. exact match는 값을 찾을 때, lower bound와 upper bound는 경계를 찾을 때, first true는 답 공간을 탐색할 때 자주 쓰입니다.
def binary_search(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1def lower_bound(nums, target):
left = 0
right = len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
def upper_bound(nums, target):
left = 0
right = len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] > target:
right = mid
else:
left = mid + 1
return leftdef first_true(low, high, can_do):
left = low
right = high
while left < right:
mid = left + (right - left) // 2
if can_do(mid):
right = mid
else:
left = mid + 1
return left이제 같은 감각을 C, Python, Java로 각각 한 번씩 보겠습니다. 예시는 실전에서 가장 자주 재사용되는 lower bound와 first true 패턴 위주로 잡았습니다.
언어별 예시
C
#include <stdbool.h>
#include <stdio.h>
int lower_bound(int arr[], int n, int target) {
int left = 0;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
bool can_do(int speed, int jobs[], int n, int limit) {
long long total = 0;
for (int i = 0; i < n; i++) {
total += (jobs[i] + speed - 1) / speed;
}
return total <= limit;
}
int first_true(int low, int high, int jobs[], int n, int limit) {
int left = low;
int right = high;
while (left < right) {
int mid = left + (right - left) / 2;
if (can_do(mid, jobs, n, limit)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}Python
def lower_bound(nums, target):
left = 0
right = len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
def min_speed(jobs, limit):
def can_do(speed):
total = 0
for job in jobs:
total += (job + speed - 1) // speed
return total <= limit
left = 1
right = max(jobs)
while left < right:
mid = left + (right - left) // 2
if can_do(mid):
right = mid
else:
left = mid + 1
return leftJava
public class BinarySearchPatterns {
static int lowerBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
static boolean canDo(int speed, int[] jobs, int limit) {
long total = 0;
for (int job : jobs) {
total += (job + speed - 1) / speed;
}
return total <= limit;
}
static int firstTrue(int low, int high, int[] jobs, int limit) {
int left = low;
int right = high;
while (left < right) {
int mid = left + (right - left) / 2;
if (canDo(mid, jobs, limit)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}한 줄 연결
- exact match: 값 하나를 찾는다
- lower bound: 조건을 처음 만족하는 위치를 찾는다
- upper bound: 그 다음 경계를 찾는다
- answer search: 배열 대신 답의 범위에서 처음 만족하는 값을 찾는다
- parametric search: 판별 함수의 단조성을 이용해 answer search를 수행한다
결국 모두 같은 축입니다. 경계가 어디서 바뀌는가를 찾는 일입니다.
자주 틀리는 점
- 배열이 없는 answer search에서도 exact match 감각으로 접근하는 실수
- 단조성을 확인하지 않고 이분 탐색부터 쓰는 실수
- left <= right 와 left < right 를 섞어 쓰며 off-by-one 버그를 만드는 실수
특히 판별 결과가 false true false true처럼 왔다 갔다 하면 한쪽 절반 전체를 버릴 수 없습니다. 이 경우에는 이분 탐색이 성립하지 않습니다.
그래서 코드를 외우기보다 내가 찾는 것이 값인지, 첫 true인지, 마지막 true인지를 먼저 분명히 하는 편이 훨씬 안전합니다.
언제 떠올릴까
- 정렬된 배열에서 처음이나 마지막 위치를 찾는다
- 어떤 값 이상 또는 이하의 첫 위치를 찾는다
- 최소 가능한 값이나 최대 가능한 값을 찾는다
- 어떤 값이 가능한지 여부를 판별할 수 있다
- 가능/불가능 경계가 한 번만 바뀐다
문제 문장에 최소, 최대, 처음, 마지막, 가능한가, 제한 안에 되는가 같은 표현이 보이면 정답을 직접 만드는 대신 경계를 찾는 문제인지 먼저 의심해볼 만합니다.
정리
이분탐색(binary search)은 정렬된 배열에서 숫자를 찾는 알고리즘으로 끝나지 않습니다. 더 중요한 본질은 조건이 바뀌는 경계를 찾는 사고법이라는 점입니다.
lower bound와 upper bound를 이해하면 중복 값 처리와 경계 탐색이 쉬워지고, first true와 parametric search까지 연결하면 배열 바깥의 값 공간에서도 같은 원리를 쓸 수 있게 됩니다.
이분 탐색을 잘한다는 것은 가운데를 잘 찍는 것이 아니라, 어디서 조건이 바뀌는지 보고 한쪽 절반을 버릴 근거를 찾는 것입니다.
관련해서 범위를 줄이는 다른 사고법은 투 포인터 알고리즘이란 무엇인가, 접근 방향 판단은 애드혹 알고리즘 접근법, 완전탐색 기초는 브루트포스 알고리즘 글도 함께 보면 흐름이 더 잘 잡힙니다. 외부 참고 자료로는 Python bisect 공식 문서와 USACO Guide의 Binary Search 정리가 도움이 됩니다.
