---
title: "이진 탐색: 반열린 구간 불변식으로 첫 위치까지 찾는 Java 구현"
slug: "java-binary-search"
category: "CS"
topic: "cs"
subtopic: "algorithms"
tags: ["Java","Binary Search","Lower Bound","Sorted Array","Invariant"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "정렬 전제와 반열린 후보 구간을 명시하고, lower bound에서 첫 중복 위치·삽입 위치·overflow-safe midpoint가 왜 맞는지 증명한다."
kind: "Deep Dive"
evidence: "Princeton Algorithms 4/e Binary Search·Oracle Arrays.binarySearch 계약·JLS/JVMS 21을 대조하고 BinarySearchDemo를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

이진 탐색의 핵심은 가운데를 보는 행위가 아니다. **정렬 관계를 근거로 답이 될 수 없는 절반을 버리는 것**이다. 따라서 정렬되지 않은 입력에 같은 loop를 돌리는 코드는 느린 것이 아니라 틀린 코드다.

## 1. 문제 계약: lower bound를 기본 연산으로 잡는다

입력은 오름차순 `int[] sorted`와 `target`이다. `lowerBound`는 `sorted[i] >= target`을 만족하는 가장 작은 index를 반환한다. 그런 원소가 없으면 `sorted.length`를 반환한다. `firstIndexOf`는 그 index의 값이 target인지 확인해 첫 중복 위치나 `-1`을 반환한다.

Oracle `Arrays.binarySearch`는 값이 있으면 index를 주지만 중복 중 어느 index인지는 보장하지 않는다. 없으면 음수로 encoding한 insertion point를 준다. 첫 위치가 필요하면 lower bound 계약을 직접 사용해야 한다.

## 2. 쓰지 않으면, 또는 잘못 쓰면

정적 정렬 배열에 반복 질의하면서 매번 선형 scan하면 최악 $qn$번 비교한다. 이진 탐색은 질의당 후보 수를 절반으로 줄인다. 반대로 한 번 찾기 위해 정렬부터 하면 전처리 $O(n\log n)$이 scan보다 비싸고 원본 순서까지 바꿀 수 있다.

정렬 전제를 런타임마다 검사하면 검사 자체가 $O(n)$이라 이진 탐색의 이점을 없앤다. 보통 정렬을 보장하는 생성 경계에서 한 번 검증하고, 검색 method는 그 타입/모듈 계약을 믿는다.

## 3. `[left,right)` 상태를 추적한다

`[3,7,7,7,19]`에서 target 7의 lower bound를 찾는다.

| 단계 | `[left,right)` | `middle` 값 | 판단 | 다음 구간 |
| ---: | --- | ---: | --- | --- |
| 0 | `[0,5)` | index 2 = 7 | `>= target`, 2 이후는 첫 위치 아님 | `[0,2)` |
| 1 | `[0,2)` | index 1 = 7 | `>= target` | `[0,1)` |
| 2 | `[0,1)` | index 0 = 3 | `< target`, 0 이하는 탈락 | `[1,1)` |

**불변식:** `[0,left)`의 모든 값은 target보다 작고, `[right,n)`의 모든 값은 target 이상이다. 따라서 lower bound 후보는 항상 `[left,right)`에 있다.

- 초기에는 두 바깥 구간이 비어 있어 참이다.
- `sorted[middle] < target`이면 정렬 때문에 middle 이하도 모두 작으므로 `left=middle+1`이 안전하다.
- 그렇지 않으면 middle 이상이 첫 위치일 수 없거나 첫 위치를 포함한 오른쪽 경계이므로 `right=middle`이 안전하다.
- 종료 시 `left==right`; 후보 구간은 비었고 두 바깥 조건이 맞닿는 index가 첫 `>= target` 위치다.

## 실행 재현

아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

```java
public final class BinarySearchDemo {
    static int lowerBound(int[] sorted, int target) {
        if (sorted == null) throw new IllegalArgumentException("sorted must not be null");
        int left = 0;
        int right = sorted.length;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (sorted[middle] < target) left = middle + 1;
            else right = middle;
        }
        return left;
    }

    static int firstIndexOf(int[] sorted, int target) {
        int index = lowerBound(sorted, target);
        return index < sorted.length && sorted[index] == target ? index : -1;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        int[] sorted = {3, 7, 7, 7, 19, Integer.MAX_VALUE};
        check(firstIndexOf(sorted, 7) == 1, "first duplicate");
        check(lowerBound(sorted, 8) == 4, "insertion point");
        check(firstIndexOf(sorted, 8) == -1, "missing");
        check(firstIndexOf(new int[0], 1) == -1, "empty");
        check(firstIndexOf(sorted, Integer.MAX_VALUE) == 5, "max int");
        System.out.println("first(7)=1, lowerBound(8)=4, missing=-1");
    }
}
```

```bash
javac --release 21 BinarySearchDemo.java
java BinarySearchDemo
```

직접 실행한 출력은 다음과 같다.

```text
first(7)=1, lowerBound(8)=4, missing=-1
```

컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다.


## 4. 종료와 overflow를 별도로 증명한다

loop가 실행될 때 `left < right`이므로 `middle`은 `[left,right)` 안이다. 어느 분기든 새 구간 길이는 이전보다 작다. 0 이상의 정수 길이가 계속 감소하므로 종료한다.

`(left + right) / 2`는 두 index 합이 `int` 범위를 넘으면 wraparound할 수 있다. Java 정수 연산은 overflow를 예외로 알리지 않는다. `left + (right-left)/2`는 유효 index 범위에서 합산 overflow를 피한다. 실제 Java 배열은 메모리 제한 때문에 극단값 재현이 어려워도, 경계식 자체는 올바르게 작성해야 한다.

## 5. 복잡도 유도

$k$번 반복 뒤 후보 수는 최대 $n/2^k$다. 후보가 1 이하가 되려면 다음 조건을 만족한다.

$$
\frac{n}{2^k}\le1 \Rightarrow k\ge\log_2 n
$$

따라서 비교 횟수는 $O(\log n)$이고 최악·평균이 같은 차수다. local index 세 개 외에 새 자료구조를 만들지 않으므로 보조 공간은 $O(1)$이다. 재귀 구현은 깊이 $O(\log n)$의 method frame을 추가하므로 Java에서는 단순 반복형이 더 직접적이다.

## 6. JVM 메모리와 실제 성능

`sorted` array는 heap object, local references와 index는 현재 frame의 local variable이다. loop는 allocation하지 않고 primitive `int`를 읽는다. 이론상 $O(\log n)$이어도 큰 배열의 접근 index가 멀리 뛰어 cache miss가 생길 수 있다. 작은 배열의 linear scan이 branch와 locality 덕분에 더 빠른 구간도 있을 수 있으므로 JMH로 crossover를 측정한다.

`List<Integer>`에 같은 알고리즘을 일반화할 때 `ArrayList`의 random access와 `LinkedList`의 index 접근 비용은 다르다. `Collections.binarySearch` API 문서도 random-access가 아닌 큰 list에 iterator 기반 전략을 사용한다고 명시한다. 자료 표현을 무시한 복잡도 표기는 불완전하다.

## 7. 변형은 반환 계약에서 나온다

| 변형 | 경계 조건 | 결과 |
| --- | --- | --- |
| lower bound | 첫 `>= target` | 첫 중복 또는 삽입 위치 |
| upper bound | 첫 `> target` | 마지막 중복 다음 위치 |
| exact any | `==`면 즉시 반환 | 중복 중 임의 위치 |
| monotone answer | predicate가 false→true | 조건을 처음 만족하는 값 |

“정답에 대한 이진 탐색”도 값 배열이 아니라 단조 predicate의 경계를 찾는 같은 구조다. capacity, deadline처럼 정답 영역이 연속일 때만 쓸 수 있다.

## 8. 실제 도메인 적용

정적 routing table snapshot, versioned timestamp index, SSTable block index처럼 읽기가 많고 정렬 snapshot이 유지되는 곳에 맞는다. 관측 지표는 query count, rebuild duration, update lag, p99 lookup latency다. DB B-tree는 단순 배열 이진 탐색과 다르며 page I/O, fan-out, lock/MVCC 비용까지 execution plan으로 봐야 한다.

## 9. 이건 피한다

- **정렬되지 않은 데이터를 그대로 검색한다.** 절반 제거 근거가 없어 false negative가 발생한다. 생성 경계에서 정렬을 보장하거나 선형/hash 탐색을 쓴다.
- **중복인데 아무 index를 첫 위치로 사용한다.** `Arrays.binarySearch`는 중복 선택을 보장하지 않는다. lower/upper bound 계약을 구현한다.
- **한 번 질의하려고 입력을 정렬한다.** 전처리와 순서 파괴가 더 비싸다. 반복 질의 수와 update cost를 계산한다.
- **`left + right`로 middle을 만든다.** int overflow로 음수 index가 될 수 있다. 차이를 먼저 나누는 식을 쓴다.
- **linked list에 index 기반 loop를 복사한다.** 각 `get(mid)`가 선형이면 전체 비용이 악화된다. random-access 배열로 바꾸거나 iterator 전략을 사용한다.

## Reference

- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Binary Search](https://algs4.cs.princeton.edu/11model/#binarysearch)
- Oracle, [Arrays.binarySearch — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html#binarySearch(int%5B%5D,int))
- Oracle, [Collections.binarySearch — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Collections.html#binarySearch(java.util.List,T))
- Oracle, [The Java Language Specification, Java SE 21 — Integer Operations](https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2.2)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Frames and Heap](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)