[도구, Binary Search] 이분탐색의 세 가지 경우

이분탐색 문제를 풀다보면,

1. 일반적인 이분탐색
2. 최솟값 찾기
3. 최댓값 찾기

세 가지 경우 문제가 존재한다.

각 경우를 정리해보자.

1. 일반적인 이분탐색

int left = 0;
int right = arr.length - 1; // 범위의 마지막 값

while (left <= right) {
    mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return mid;     // 찾는 값 발견
    } else if (nums[mid] < target) {
        left = mid + 1; // 오른쪽 절반 탐색
    } else {
        right = mid - 1; // 왼쪽 절반 탐색
    }
}
return -1; // 못찾음

특징

1. left <= right 조건을 사용
2. 구간이 mid - 1 또는 mid + 1로 이동
   • mid값은 이미 확인했으므로 다음 탐색에서 제외
3. 주로 사용하는 경우
   • 정렬된 배열에서 특정 값 찾기
   • 정확한 값의 존재 여부 확인
   • 배열에서 target이 있는 index 찾기

---

2. 최솟값 찾기

int left = 최소가능값;
int right = 최대가능값 + 1; // 열린 범위로

while (left < right) {
    mid = left + (right - left) / 2;
    if (condition(mid)) {
        right = mid;    // 조건 만족하면 더 작은 값 가능한지 확인
    } else {
        left = mid + 1; // 조건 불만족하면 더 큰 값 필요
    }
}
return left; // left == right가 됨

특징

1. left < right 조건을 사용
   • 최종적으로 left와 right가 같아지는 지점이 답
   • 범위를 좁혀가며 최솟값을 찾음
2. 조건 만족 시 right = mid
   • mid값이 가능한 답이므로 버리지 않음
3. 주로 사용하는 경우
   • 최솟값 찾기 문제
   • 조건을 만족하는 첫 번째 위치 찾기
   • 특정 조건을 만족하는 경계값 찾기

---

3. 최댓값 찾기

int left = 최소가능값;
int right = 최대가능값;

while (left < right) {
    // mid를 올림으로 계산 (이게 핵심!)
    mid = left + (right - left + 1) / 2;
    
    if (condition(mid)) {
        left = mid;     // 조건 만족하면 더 큰 값 가능한지 확인
    } else {
        right = mid - 1; // 조건 불만족하면 더 작은 값 필요
    }
}
return left; // 또는 right (같은 값)

2번과 차이점

1. mid 계산할 때 올림으로 계산 (+1 추가)
2. 조건 만족 시 left = mid로 오른쪽 탐색
3. 조건 불만족시 right = mid - 1로 왼쪽 탐색