Binary search와 그 변형: lower bound, 회전 배열, 답 탐색

1. 개요

Binary search는 이미 정렬된 데이터에서 O(log n) 복잡도로 탐색하는 알고리즘입니다. 아이디어는 매우 간단하지만, 구현하기는 쉽지 않습니다: 무한 루프, off-by-one 오류, mid 계산 시 오버플로우.

이 글은 기본 버전에서 시작하여 자주 나오는 변형들을 다룹니다: 중복 요소의 첫 번째/마지막 위치 찾기, 출현 횟수 세기, 회전된 배열에서 찾기, 답 탐색 binary search. 끝내고 나면 오류가 적은 구현 틀 한 세트와 검증을 위한 테스트를 갖게 될 것입니다.

2. 기본 binary search

상품 가격이 오름차순으로 정렬된 배열이 있고 특정 가격의 위치를 찾아야 한다고 가정해봅시다:

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

설명:

• lo와 hi는 닫힌 구간 [lo, hi]을 만듭니다. 이것이 target이 있을 수 있는 영역입니다.
• lo <= hi 조건은 구간에 최소한 하나의 요소가 있을 때 루프가 계속 실행됨을 의미합니다.
• mid = lo + (hi - lo) / 2은 오버플로우를 피합니다. (lo + hi) / 2라고 쓰면 lo + hi가 Integer.MAX_VALUE를 초과할 때 오버플로우가 발생합니다. 동등한 방법은 (lo + hi) >>> 1입니다.
• 매 단계마다 구간에서 mid를 제외하므로 (mid + 1 또는 mid - 1), 구간은 항상 축소되고 루프가 확실히 종료됩니다.

결과:

3
-1

이 버전은 배열에 중복 요소가 없고 “있는가 없는가”만 알면 될 때 충분합니다. 중복 요소가 있을 때는 중복 그룹 내의 임의의 위치를 반환합니다. 대개 그것은 원하는 것이 아닙니다.

3. Lower bound와 upper bound

가장 중요한 두 가지 변형은:

• lower bound: a[i] >= target인 첫 번째 인덱스.
• upper bound: a[i] > target인 첫 번째 인덱스.

둘 다 target이 배열에 없을 때도 [0, n] 범위의 인덱스를 반환합니다. 이 인덱스는 배열을 정렬된 상태로 유지하는 삽입 위치입니다.

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // 반개 구간 [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

기본 버전과의 차이점:

• 반개 구간 [lo, hi)을 사용하므로 hi는 a.length로 초기화되고 루프 조건은 lo < hi입니다.
• a[mid]가 “충분히 크다”는 조건을 만족할 때 mid - 1이 아닌 hi = mid를 할당합니다. mid가 여전히 답일 수 있기 때문입니다.
• 두 함수는 <와 <= 부호만 다릅니다.

중복 요소가 있는 배열로 시도해봅시다:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

300의 경우 결과 4는 300을 삽입하면 350 앞에 오는 것을 의미합니다. 900의 경우 결과가 n이면 모든 요소가 더 작다는 뜻입니다.

3.1. 첫 번째 위치, 마지막 위치 및 출현 횟수

위의 두 함수로부터 친숙한 문제들을 즉시 도출할 수 있습니다:

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

위의 prices와 target = 200에서 firstIndexOf = 1, lastIndexOf = 3, count = 3을 얻습니다. 기억해야 할 점: a[i]를 읽기 전에 항상 경계 i < a.length (또는 i >= 0)을 확인하세요.

3.2. 범위 내의 요소 개수 세기

실제 적용의 예시는 [min, max] 범위의 값을 가진 주문 수를 세는 것입니다:

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

{100, 200, 200, 200, 350, 500}와 범위 [150, 400]에서 결과는? 계산해봅시다: upperBound(400) = 5, lowerBound(150) = 1, 따라서 결과는 4입니다. 각 쿼리는 O(log n)만 소비되므로 전체 배열을 순회할 필요가 없습니다.

4. 회전된 배열에서 탐색

회전된 배열은 정렬된 배열이 한 지점에서 “자르고” 두 절반을 바꾼 것입니다. 예: {40, 50, 60, 10, 20, 30}. 이 배열은 더 이상 완전히 오름차순이 아니지만 mid 주변의 적어도 한 쪽 절반은 여전히 정렬되어 있습니다. 우리는 이를 기반으로 어느 쪽으로 갈지 결정합니다:

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // 왼쪽 절반이 정렬됨
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // 오른쪽 절반이 정렬됨
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

설명:

• a[lo] <= a[mid]는 구간 [lo, mid]가 오름차순임을 나타냅니다. target이 이 구간의 값 범위에 있으면 왼쪽으로 축소합니다. 그렇지 않으면 오른쪽으로 갑니다.
• 그 외의 경우 구간 [mid, hi]가 오름차순이고, 대칭적으로 논리를 적용합니다.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

주의: 이 구현은 배열에 중복 요소가 없다고 가정합니다. {2, 2, 2, 3, 2}와 같은 배열의 경우 a[lo] <= a[mid] 조건은 어느 쪽이 정렬되어 있는지 구분할 수 없습니다. 이 경우 a[lo] == a[mid]를 처리하기 위해 lo를 한 단위씩 증가시켜야 하며, 최악의 복잡도는 O(n)이 됩니다.

5. 답 탐색 Binary search

이것이 가장 강력한 변형입니다. 배열에서 찾는 것이 아니라 조건을 만족하는 최솟값을 찾습니다. 적용하기 위한 유일한 조건은 predicate가 단조여야 한다는 것입니다: x가 만족하면 x보다 큰 모든 값도 만족합니다. 다시 말해, 결과 시퀀스는 false, false, ..., true, true 형태입니다.

일반적인 함수를 작성합시다:

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** [lo, hi]에서 ok가 true를 반환하는 최솟값. ok(hi) == true라고 가정합니다. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

이 함수는 lowerBound와 같은 구조입니다. 사실 lowerBound는 predicate a[i] >= target인 특수한 경우일 뿐입니다.

실제 문제에 적용하면: 창고에 정해진 순서대로 소포 목록이 있고 maxDays 일 안에 배송을 끝내야 합니다. 매일 트럭은 연속된 소포를 운반하며, 총 무게는 트럭의 적재 용량을 초과할 수 없습니다. 최소 적재 용량은 얼마일까요?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

설명:

• lo는 가장 무거운 소포입니다. 트럭은 최소한 어떤 소포든 운반할 수 있어야 하기 때문입니다. hi는 총 무게입니다. 이 경우 하루만 필요하기 때문입니다. 따라서 ok(hi)는 확실히 참입니다.
• canShip은 탐욕적으로 시뮬레이션합니다: 적재량을 초과할 때까지 소포를 트럭에 싣고, 그러면 다음 날로 넘어갑니다. 용량이 클수록 필요한 일 수가 적으므로 predicate는 단조입니다.
• 총 비용은 O(n · log(sum))입니다. 각 용량을 시도하는 것 대신에 말입니다.

6

용량 6으로 배송 일정은 [3, 2], [2, 4], [1, 4]로 정확히 3일입니다. 용량 5로는 4일이 필요하므로 5는 조건을 만족하지 않습니다.

같은 틀로 많은 다른 문제를 풀 수 있습니다: 배치를 시간 내에 처리하기 위한 최소 스레드 수, 최소 rate 제한, 정수의 정수 제곱근.

6. Java 표준 라이브러리 사용

Java는 이미 Arrays.binarySearch와 Collections.binarySearch를 제공합니다. 반환 값을 명확히 이해해야 합니다:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• 발견했을 때 함수는 요소의 인덱스를 반환합니다.
• 발견하지 못했을 때 함수는 -(insertionPoint) - 1을 반환합니다. 여기서 삽입 위치는 4이므로 결과는 -5입니다. 삽입 위치를 다시 얻으려면 -(result) - 1을 계산합니다.
• 중복 요소가 있을 때 문서는 중복 그룹 내의 어느 위치를 반환할지 보장하지 않습니다. 첫 번째 또는 마지막 위치가 필요하면 자신의 lowerBound/upperBound를 사용하세요.

객체 목록의 경우 정렬된 순서와 일치하는 Comparator를 전달합니다:

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

주의: LinkedList의 Collections.binarySearch는 인덱스 접근이 O(n)이므로 O(log n)을 달성하지 못합니다. ArrayList 또는 배열을 사용하세요.

7. 테스팅

JUnit 5와 AssertJ를 의존성에 추가하세요. 프로젝트가 spring-boot-starter-test를 사용하면 둘 다 이미 포함됩니다.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

경계 사례에 대한 테스트를 작성하세요. 여기가 binary search가 가장 자주 실패하는 곳입니다:

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

lowerBoundMatchesLinearScan 테스트는 빈 배열을 포함한 1,000개의 무작위 배열에 대해 선형 카운팅과 비교합니다. 이 비교 테스트 유형은 손으로 작성한 몇 가지 예보다 off-by-one 오류를 훨씬 잘 잡습니다.

8. 흔한 오류 및 사용하지 말아야 할 때

흔한 오류:

• 두 구간 규칙 혼용. hi = n(반개)로 초기화하지만 while (lo <= hi) 루프를 사용하고 hi = mid - 1을 할당합니다. 결과는 배열 밖을 읽습니다. 한 규칙을 선택하고 일관되게 유지하세요.
• 무한 루프. lo = mid를 mid = (lo + hi) / 2와 함께 작성하면 hi = lo + 1일 때 mid == lo이고 구간이 축소되지 않습니다. 정말 lo = mid가 필요하면 올림: mid = lo + (hi - lo + 1) / 2.
• 오버플로우 mid 계산이나 답 탐색 binary search에서 합을 계산할 때. 큰 값에는 long을 사용하세요.
• 비단조 predicate. Binary search는 여전히 숫자를 반환하지만 그 숫자는 의미가 없습니다. 적용하기 전에 단조성을 증명하세요.

사용하지 말아야 할 때:

• 데이터가 정렬되지 않았고 몇 번만 찾습니다. 정렬은 O(n log n)이지만 선형 탐색은 O(n)입니다.
• 많은 탐색으로 “있는가 없는가”만 확인하면 됩니다. 그러면 HashSet은 평균 O(1)을 제공합니다.
• 데이터가 자주 변경되고 많은 삽입과 삭제가 필요합니다. 배열 정렬 유지는 삽입당 O(n)입니다. TreeMap/TreeSet을 고려하세요. 이들은 이미 ceilingKey, floorKey, higherKey를 가지고 있어 lower bound와 upper bound와 같습니다.
• 배열이 매우 작고 수십 개의 요소만 있습니다. 선형 순회는 캐시 덕분에 보통 같거나 더 빠르고, 코드가 더 간단합니다.

9. 결론

Binary search는 단지 “배열에서 요소 찾기”가 아닙니다. 반개 구간 [lo, hi)로 lower bound와 upper bound를 이해하면 첫 번째/마지막 위치, 요소 세기 및 범위별 세기 문제를 단 몇 줄로 해결할 수 있습니다. 회전 배열은 정렬된 절반을 확인하는 추가 단계가 필요합니다. 답 탐색 binary search는 모든 단조 predicate 문제로 기법을 확장합니다.

단일 구간 규칙을 유지하고 >>>나 lo + (hi - lo) / 2를 사용하여 오버플로우를 피하며 항상 선형 탐색과 비교하는 테스트를 작성하세요. 이 세 가지 습관은 binary search가 여전히 유명한 오류를 거의 제거합니다.