Theme:

이진 탐색 심화 — lower_bound 하나 못 짜서 틀리는 이유

알고리즘이진 탐색
2026-05-03·8 min read

이진 탐색은 쉽다고 생각했는데, lower_bound를 직접 짜보면 off-by-one 에러에 빠집니다. 왜 그런 걸까요?

이진 탐색 기본

이진 탐색(Binary Search)은 정렬된 배열 에서 원하는 값을 O(log n)에 찾는 알고리즘입니다. 매 단계마다 탐색 범위를 절반으로 줄입니다.

JAVA
public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 오버플로우 방지

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 못 찾음
}

왜 이진 탐색이 어려운가

이진 탐색의 기본 개념은 단순하지만, 실제 구현에서 다음과 같은 함정이 있습니다.

  1. **경계 조건 **: left <= right vs left < right
  2. **mid 계산 **: (left + right) / 2 vs left + (right - left) / 2
  3. ** 포인터 이동 **: left = mid vs left = mid + 1
  4. ** 반환값 **: 정확히 일치하는 값 vs 가장 가까운 값

이 혼란의 근본 원인은 "무엇을 찾는가"에 따라 구현이 달라지기 때문 입니다.

lower_bound와 upper_bound

lower_bound: target 이상인 첫 번째 위치

JAVA
// arr에서 target 이상인 값이 처음 나타나는 인덱스
// 모든 원소가 target보다 작으면 arr.length 반환
public static int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < target) {
            left = mid + 1;  // mid는 확실히 답이 아님
        } else {
            right = mid;     // mid가 답일 수 있음
        }
    }
    return left;
}

핵심 포인트:

  • right = arr.length (배열 끝 다음)로 초기화
  • left < right 조건 사용 (left == right이면 답)
  • arr[mid] >= target이면 right = mid (mid를 후보로 유지)

upper_bound: target 초과인 첫 번째 위치

JAVA
// arr에서 target보다 큰 값이 처음 나타나는 인덱스
public static int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

lower_bound와의 차이는 딱 하나: arr[mid] < target → arr[mid] <= target.

활용 예제

JAVA
int[] arr = {1, 2, 2, 2, 3, 4, 5};

// target=2의 개수
int count = upperBound(arr, 2) - lowerBound(arr, 2); // 4 - 1 = 3

// target=2가 있는지 확인
int lb = lowerBound(arr, 2);
boolean exists = lb < arr.length && arr[lb] == 2; // true

// target=2.5 이상인 첫 원소
int idx = lowerBound(arr, 3); // 4 → arr[4] = 3

자주 틀리는 패턴과 해결

패턴 1: left <= right에서의 무한 루프

JAVA
// 잘못된 코드 — 무한 루프!
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] < target) {
        left = mid; // mid + 1이 아님!
    } else {
        right = mid; // mid - 1이 아님!
    }
}
// left == right == mid일 때 어느 쪽도 변하지 않아 무한 루프

패턴 2: 반열린 구간 vs 닫힌 구간

구간초기값반복 조건이동
닫힌 [left, right]left=0, right=n-1left <= rightmid±1
반열린 [left, right)left=0, right=nleft < rightleft=mid+1 or right=mid

lower_bound/upper_bound는 반열린 구간 이 자연스럽습니다. 결과가 배열 범위 밖(n)일 수 있기 때문입니다.

패턴 3: 최댓값 찾기에서의 mid 계산

최댓값(마지막으로 조건을 만족하는 위치)을 찾을 때 mid = left + (right - left + 1) / 2로 올림해야 무한 루프를 피할 수 있습니다.

JAVA
// target 이하인 마지막 위치
public static int lastLessOrEqual(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left < right) {
        int mid = left + (right - left + 1) / 2; // 올림!

        if (arr[mid] <= target) {
            left = mid;     // mid가 답일 수 있음
        } else {
            right = mid - 1;
        }
    }
    return left;
}

파라메트릭 서치(Parametric Search)

파라메트릭 서치는 최적화 문제를 결정 문제로 변환 하여 이진 탐색을 적용하는 기법입니다.

"최솟값/최댓값을 구하라" → "이 값이 가능한가? (Yes/No)"

예제: 나무 자르기

나무를 높이 H에서 잘랐을 때, 잘린 부분의 합이 M 이상이 되는 최대 H를 구하세요.

JAVA
public static long maxCutHeight(long[] trees, long target) {
    long left = 0, right = Arrays.stream(trees).max().getAsLong();

    while (left < right) {
        long mid = left + (right - left + 1) / 2; // 올림 (최댓값 찾기)

        if (canCut(trees, mid, target)) {
            left = mid;     // mid 높이로 잘라도 충분 → 더 높이 잘라보기
        } else {
            right = mid - 1; // 부족 → 더 낮게
        }
    }
    return left;
}

private static boolean canCut(long[] trees, long height, long target) {
    long sum = 0;
    for (long tree : trees) {
        if (tree > height) {
            sum += tree - height;
        }
    }
    return sum >= target;
}

예제: 최소 시간으로 모든 작업 완료

K개의 기계로 N개의 작업을 처리할 때, 최소 시간을 구하는 문제입니다.

JAVA
public static long minTime(long[] machines, long n) {
    long left = 1, right = Arrays.stream(machines).min().getAsLong() * n;

    while (left < right) {
        long mid = left + (right - left) / 2;

        if (canFinish(machines, mid, n)) {
            right = mid;    // 가능 → 더 짧은 시간 시도
        } else {
            left = mid + 1; // 불가능 → 더 긴 시간 필요
        }
    }
    return left;
}

private static boolean canFinish(long[] machines, long time, long n) {
    long total = 0;
    for (long m : machines) {
        total += time / m;
        if (total >= n) return true; // 오버플로우 방지
    }
    return false;
}

Java의 내장 이진 탐색

Arrays.binarySearch

JAVA
int[] arr = {1, 3, 5, 7, 9};
int idx = Arrays.binarySearch(arr, 5);  // 2
int notFound = Arrays.binarySearch(arr, 4); // -(2) - 1 = -3
// 삽입 위치 = -(notFound) - 1 = 2 → arr[2] = 5 앞에 삽입

Collections.binarySearch

JAVA
List<Integer> list = List.of(1, 3, 5, 7, 9);
int idx = Collections.binarySearch(list, 7); // 3

**주의 **: 중복 원소가 있을 때 어떤 인덱스가 반환될지 보장되지 않습니다. 특정 위치가 필요하면 직접 lower_bound를 구현해야 합니다.

백엔드/실무에서의 연결

DB 인덱스 탐색

B-Tree 인덱스에서 특정 값을 찾는 과정은 이진 탐색의 일반화입니다. 각 노드에서 키를 이진 탐색하여 다음 자식 노드를 결정합니다.

SQL
-- 범위 검색: lower_bound와 upper_bound의 DB 버전
SELECT * FROM orders WHERE amount BETWEEN 1000 AND 5000;
-- B-Tree에서 1000의 lower_bound를 찾고, 5000의 upper_bound까지 순차 탐색

API의 페이지네이션

커서 기반 페이지네이션에서 다음 페이지의 시작점을 결정할 때, 인덱스를 통한 이진 탐색이 내부적으로 사용됩니다.

시스템 설정 튜닝

"최적의 스레드 수", "적정 배치 크기" 같은 값을 찾을 때 파라메트릭 서치 사고방식이 유용합니다. 이분 탐색으로 "이 값이 충분한가?"를 반복 테스트합니다.

로그 파일에서 특정 시간대 찾기

시간순으로 정렬된 로그에서 특정 시간 범위를 찾을 때 이진 탐색을 사용합니다.

주의할 점

left <= right vs left < right 혼동

값을 찾는 기본 이진 탐색은 left <= right, lower_bound/upper_bound는 left < right를 사용합니다. 이 조건을 섞으면 무한 루프나 off-by-one 에러가 발생합니다.

최댓값 찾기에서 mid 올림을 빠뜨려 무한 루프

left = mid로 이동하는 경우, mid = left + (right - left) / 2는 내림이라 left == mid가 되어 무한 루프에 빠집니다. 반드시 mid = left + (right - left + 1) / 2로 올림해야 합니다.

Java의 binarySearch가 중복 원소 위치를 보장하지 않는 것을 모르는 실수

Arrays.binarySearch는 중복 원소가 있을 때 어떤 인덱스가 반환될지 보장하지 않습니다. 특정 위치(첫 번째, 마지막)가 필요하면 직접 lower_bound를 구현해야 합니다.

정리

유형조건초기화이동 방식
값 찾기left <= right[0, n-1]mid±1
lower_boundleft < right[0, n)left=mid+1 or right=mid
upper_boundleft < right[0, n)left=mid+1 or right=mid
최댓값 (파라메트릭)left < right문제에 따라mid 올림 + left=mid

기억할 포인트:

  • lower_bound = "target 이상 인 첫 위치", upper_bound = "target 초과 인 첫 위치"
  • mid = left + (right - left) / 2로 오버플로우를 방지하세요.
  • 최댓값을 찾을 때는 mid를 올림 해야 무한 루프를 피합니다.
  • 파라메트릭 서치는 "최적화 → 결정 문제"로 바꾸는 강력한 도구입니다.
  • Java의 Arrays.binarySearch는 중복 원소의 위치를 보장하지 않습니다. 필요하면 직접 구현하세요.
related posts
댓글 로딩 중...
On This Page
이진 탐색 기본왜 이진 탐색이 어려운가lower_bound와 upper_boundlower_bound: target 이상인 첫 번째 위치upper_bound: target 초과인 첫 번째 위치활용 예제자주 틀리는 패턴과 해결패턴 1: left <= right에서의 무한 루프패턴 2: 반열린 구간 vs 닫힌 구간패턴 3: 최댓값 찾기에서의 mid 계산파라메트릭 서치(Parametric Search)예제: 나무 자르기예제: 최소 시간으로 모든 작업 완료Java의 내장 이진 탐색Arrays.binarySearchCollections.binarySearch백엔드/실무에서의 연결DB 인덱스 탐색API의 페이지네이션시스템 설정 튜닝로그 파일에서 특정 시간대 찾기주의할 점left <= right vs left < right 혼동최댓값 찾기에서 mid 올림을 빠뜨려 무한 루프Java의 binarySearch가 중복 원소 위치를 보장하지 않는 것을 모르는 실수정리