Quick Syntax
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;정렬된 배열에서 값 하나를 찾을 때는 닫힌 구간, 첫 조건 만족 위치를 찾을 때는 반열린 구간과 lower bound를 사용합니다.
구조
이진 탐색은 후보 범위의 가운데를 확인하고, 답이 있을 수 없는 절반을 버립니다. 그래서 한 번 반복할 때마다 범위가 절반이 되어 O(log n)에 끝납니다.
전제는 정렬입니다. 더 넓게 보면 정렬 배열이 아니어도 “왼쪽은 false, 오른쪽은 true”처럼 조건이 단조적으로 바뀌면 이진 탐색을 쓸 수 있습니다.
false false false true true true
^
첫 true 찾기lower bound
lower bound는 target 이상이 처음 나오는 위치입니다.
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) left = mid + 1;
else right = mid;
}
return left;
}right를 포함하지 않는 구간 [left, right)로 잡으면 삽입 위치를 찾기 좋습니다.
int index = LowerBound(values, target);
bool exists = index < values.Length && values[index] == target;빈 배열에서도 LowerBound와 UpperBound는 0을 반환합니다. target이 배열에 없을 때도 lower bound는 삽입 위치를 반환하므로, 실제 존재 여부는 위처럼 index와 값을 함께 확인해야 합니다.
static int UpperBound(int[] values, int target)
{
int left = 0;
int right = values.Length;
while (left < right)
{
int middle = left + (right - left) / 2;
if (values[middle] <= target) left = middle + 1;
else right = middle;
}
return left;
}
static int FirstTrue(int low, int high, Func<int, bool> can)
{
while (low < high)
{
int middle = low + (high - low) / 2;
if (can(middle)) high = middle;
else low = middle + 1;
}
return low;
}LowerBound는 target 이상 첫 index, UpperBound는 target 초과 첫 index를 반환합니다. FirstTrue는 [low, high] 안에 true가 적어도 하나 있다는 전제에서만 답을 반환합니다. 답이 없을 수 있으면 can(high)를 먼저 확인하거나 별도 sentinel을 둡니다.
선택 기준
| 상황 | 판단 |
|---|---|
| 정렬 배열에서 값 찾기 | 기본 이진 탐색 |
| 첫 번째 이상 위치 | lower bound |
| 첫 번째 초과 위치 | upper bound |
| 답의 범위가 숫자이고 가능 여부가 단조 | parametric search |
| 정렬되지 않은 데이터 | 먼저 정렬하거나 다른 구조 검토 |
코테에서 “최댓값의 최솟값”, “최솟값의 최댓값” 같은 표현은 답을 이진 탐색하는 문제일 수 있습니다. 이 경우 핵심은 Can(value) 함수를 단조 조건으로 만들 수 있는지입니다.
주의할 점
mid = (left + right) / 2는 값이 매우 클 때 overflow 위험이 있습니다. left + (right - left) / 2 형태가 안전합니다.
또 left <= right와 left < right 방식은 경계 업데이트가 다릅니다. 두 스타일을 섞으면 무한 루프나 한 칸 누락이 생기기 쉽습니다.
참고 링크
1 sources