숏컷 코드
csharp
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;구조
이진 탐색은 후보 범위의 가운데를 확인하고, 답이 있을 수 없는 절반을 버립니다. 그래서 한 번 반복할 때마다 범위가 절반이 되어 O(log n)에 끝납니다.
전제는 정렬입니다. 더 넓게 보면 정렬 배열이 아니어도 “왼쪽은 false, 오른쪽은 true”처럼 조건이 단조적으로 바뀌면 이진 탐색을 쓸 수 있습니다.
text
false false false true true true
^
첫 true 찾기lower bound
lower bound는 target 이상이 처음 나오는 위치입니다.
csharp
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)로 잡으면 삽입 위치를 찾기 좋습니다.
선택 기준
| 상황 | 판단 |
|---|---|
| 정렬 배열에서 값 찾기 | 기본 이진 탐색 |
| 첫 번째 이상 위치 | lower bound |
| 첫 번째 초과 위치 | upper bound |
| 답의 범위가 숫자이고 가능 여부가 단조 | parametric search |
| 정렬되지 않은 데이터 | 먼저 정렬하거나 다른 구조 검토 |
코테에서 “최댓값의 최솟값”, “최솟값의 최댓값” 같은 표현은 답을 이진 탐색하는 문제일 수 있습니다. 이 경우 핵심은 Can(value) 함수를 단조 조건으로 만들 수 있는지입니다.
주의할 점
mid = (left + right) / 2는 값이 매우 클 때 overflow 위험이 있습니다. left + (right - left) / 2 형태가 안전합니다.
또 left <= right와 left < right 방식은 경계 업데이트가 다릅니다. 두 스타일을 섞으면 무한 루프나 한 칸 누락이 생기기 쉽습니다.
참고 링크
1 sources