---
title: "선형 탐색: 정렬 없이 첫 답을 보장하는 Java 순차 스캔"
slug: "java-linear-search"
category: "CS"
topic: "cs"
subtopic: "algorithms"
tags: ["Java","Linear Search","Array","Searching","JVM"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "선형 탐색을 느린 기준선으로 치부하지 않고, 첫·마지막 위치 계약과 조기 종료 정당성, 연속 primitive 배열의 메모리 비용 및 index 구축의 손익분기점을 분석한다."
kind: "Deep Dive"
evidence: "Princeton Algorithms 4/e programming model·JLS 21 배열·JVMS 21을 대조하고 LinearSearchDemo 경계 사례를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

정렬되지 않은 배열에서 값 하나를 찾으려면 “앞에서부터 본다”가 정답일 수 있다. 선형 탐색은 느린 알고리즘의 대명사가 아니라, 사전 index가 없을 때 **검사하지 않은 원소를 건너뛰지 않는 기준선**이다.

## 1. 문제 계약: 같은 값이 여러 개면 무엇을 반환할까

입력은 `int[] values`와 `int target`이다. `firstIndexOf`는 target과 같은 **가장 작은 index**, `lastIndexOf`는 가장 큰 index를 반환한다. 없거나 배열이 비어 있으면 `-1`, `null` reference는 호출 오류로 본다.

이 계약을 “아무 index”로 흐리면 구현을 뒤에서부터 순회하거나 병렬화했을 때 호출자의 결과가 달라진다. 검색 API는 존재 여부뿐 아니라 중복 처리 순서를 명시해야 한다.

## 2. 쓰지 않으면 어떤 비용을 치르는가

정렬이 없고 값 범위에도 제약이 없으면 첫 원소를 보지 않고 그것이 target이 아니라고 결론낼 근거가 없다. HashMap을 만들면 조회는 빨라질 수 있지만 구축에 모든 원소를 읽고 $O(n)$ 보조 공간을 쓴다. 일회성 조회라면 scan 한 번보다 더 많은 일을 한다.

반대로 같은 배열에 $q$번 질의하면 매번 scan하는 최악 비용은 $qn$이다. 데이터가 오래 유지되고 질의가 많아지면 hash index나 정렬+이진 탐색의 구축 비용을 상쇄할 수 있다.

## 3. 상태와 불변식

`firstIndexOf([9,4,7,4], 4)`를 추적한다.

| `i` | 검사 값 | 검사 전 보장 | 결정 |
| ---: | ---: | --- | --- |
| 0 | 9 | `[0,0)`에는 target이 없다 | 계속 |
| 1 | 4 | `[0,1)`에는 target이 없다 | 1 반환 |

**loop 불변식:** index `i`를 검사하기 직전, 구간 `[0,i)`에는 target이 없다. 초기 `i=0`에서는 빈 구간이므로 참이다. 값이 다르면 한 원소를 검사해 `[0,i+1)`에도 없음을 보존한다. 값이 같을 때 이전 구간에는 없으므로 현재 `i`가 첫 위치다. loop가 끝나면 `[0,n)` 전체에 없으므로 `-1`이 맞다.

`lastIndexOf`는 방향을 뒤집어 `(i,n)`에 target이 없다는 불변식을 쓴다.

### 예시를 바꿔 계약 차이를 확인한다

배포 로그 `[READY, RUNNING, FAILED, RUNNING]`에서 `RUNNING`을 찾는다고 하자. 첫 위치 `1`은 “처음 실행을 시작한 시점”이고 마지막 위치 `3`은 “가장 최근 실행 상태”다. 값은 같아도 호출자가 묻는 질문이 다르므로 반환 index도 달라야 한다. 모든 위치가 필요하면 `[1,3]`을 모아야 하며, 이때 결과 크기 $k$만큼의 출력 공간은 피할 수 없다.

| 질문 | 순회 방향 | 조기 종료 | 결과 |
| --- | --- | --- | --- |
| 최초 RUNNING은 언제인가? | 앞 → 뒤 | 첫 일치 | 1 |
| 최근 RUNNING은 언제인가? | 뒤 → 앞 | 첫 일치 | 3 |
| RUNNING이 몇 번 있었나? | 전체 | 불가 | 2 |

이 예시는 “for loop 하나”도 API 계약에 따라 다른 알고리즘이 된다는 점을 보여준다. 로그가 40건이고 한 번만 묻는다면 별도 index 구축이 과하다. 같은 immutable snapshot을 수십만 번 조회한다면 매번 40개를 읽는 비용이 누적되므로 hash index나 정렬 snapshot을 검토한다. 기준은 배열 길이 하나가 아니라 **데이터 수명 동안의 전체 질의 수와 결과 계약**이다.

## 실행 재현

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

```java
public final class LinearSearchDemo {
    static int firstIndexOf(int[] values, int target) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        for (int i = 0; i < values.length; i++) {
            if (values[i] == target) return i;
        }
        return -1;
    }

    static int lastIndexOf(int[] values, int target) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        for (int i = values.length - 1; i >= 0; i--) {
            if (values[i] == target) return i;
        }
        return -1;
    }

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

    public static void main(String[] args) {
        int[] values = {9, 4, 7, 4};
        check(firstIndexOf(values, 4) == 1, "first duplicate");
        check(lastIndexOf(values, 4) == 3, "last duplicate");
        check(firstIndexOf(new int[0], 1) == -1, "empty");
        check(firstIndexOf(new int[] {Integer.MAX_VALUE}, Integer.MAX_VALUE) == 0, "boundary value");
        check(firstIndexOf(values, 8) == -1, "missing");
        System.out.println("first=1, last=3, missing=-1");
    }
}
```

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

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

```text
first=1, last=3, missing=-1
```

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


## 4. 시간 복잡도를 비교 횟수에서 유도한다

첫 원소가 답이면 한 번 비교하므로 최선 $\Theta(1)$이다. 마지막 원소가 답이거나 없으면 $n$번 비교하므로 최악 $\Theta(n)$이다. target 위치가 균등하고 항상 존재한다고 가정할 때 평균 비교 횟수는 다음과 같다.

$$
\frac{1+2+\cdots+n}{n}=\frac{n+1}{2}=\Theta(n)
$$

추가 상태는 index와 target 비교뿐이므로 알고리즘 보조 공간은 $O(1)$이다. 입력 `int[n]`을 저장하는 $O(n)$ heap 공간은 별도다.

## 5. JVM에서는 무엇이 어디에 있는가

`values` reference, `target`, `i`는 method invocation frame의 local variable 관점에서 다룬다. `int[]`는 JVMS가 정의한 heap의 array object이며 원소가 연속 primitive slot으로 저장되는 구체 layout은 JVM 구현에 의존한다. loop마다 새 객체를 만들거나 boxing하지 않는다.

이 특성 때문에 작은 연속 배열 scan은 이론상 같은 $O(n)$인 linked node 순회보다 cache locality가 좋을 수 있고, 작은 $n$에서는 HashSet 구축보다 빠를 수 있다. 다만 cache miss나 vectorization 여부는 Java 명세의 보장이 아니므로 JMH와 실제 JDK에서 측정해야 한다.

## 6. 이진 탐색·해시·DB index와 같은 계약으로 비교한다

| 선택 | 전제/구축 | 질의 | 갱신 | 보조 메모리 |
| --- | --- | ---: | ---: | ---: |
| 선형 탐색 | 없음 | $O(n)$ | 없음 | $O(1)$ |
| 정렬+이진 탐색 | 정렬 $O(n\log n)$ | $O(\log n)$ | 삽입 위치 이동 가능 | sort 방식에 따라 다름 |
| HashMap index | 구축 평균 $O(n)$ | 평균 $O(1)$ | 평균 $O(1)$ | $O(n)$ + 객체 overhead |

원본 순서를 유지해야 하고 한두 번만 찾는다면 선형 탐색이 합리적이다. 반복 질의가 지배하면 index를 만든다. DB에서는 application 배열을 내려받아 scan하지 말고, 선택도·통계·write cost를 포함해 실제 execution plan을 확인한다.

## 7. 실제 도메인 적용

- **Backend**: 요청 header 10여 개에서 특정 이름을 한 번 찾는다면 scan이 단순하다. 관측 지표는 header count와 p99 parsing time이다.
- **Data**: 작은 batch의 sentinel row 탐색은 index 구축보다 scan이 낫다. row count, early-hit position, bytes scanned를 기록한다.
- **AI**: beam 후보 수가 작을 때 조건을 만족하는 첫 후보를 찾는 scan은 추가 map을 피한다. beam width와 allocation rate를 본다.

## 8. 더 활용할 수 있는 형태

첫 위치 대신 predicate를 받으면 “첫 실패 요청”, “첫 임계치 초과 sample”을 찾을 수 있다. 모든 일치 index가 필요하면 조기 종료하지 않고 결과를 모으지만 output 크기 $k$만큼 최소 $O(k)$ 공간이 필요하다. sentinel search나 SIMD 최적화는 계약은 같지만 platform-specific 측정이 필요한 별도 주제다.

## 9. 이건 피한다

- **한 번 찾으면서 먼저 정렬한다.** 입력 순서를 파괴하고 $O(n\log n)$ 전처리를 추가한다. 반복 질의와 정렬 유지 비용이 손익분기점을 넘을 때만 선택한다.
- **중복 계약 없이 발견 즉시 반환한다.** 코드 방향에 따라 결과가 바뀐다. 첫 위치·마지막·모든 위치 중 하나를 API 이름과 테스트에 고정한다.
- **`null`을 빈 배열처럼 취급한다.** upstream 결함을 정상적인 “없음”으로 숨긴다. nullable 계약이 실제 요구일 때만 명시적으로 분기한다.
- **작은 배열에도 무조건 HashSet을 만든다.** boxing·table·node와 GC pressure가 생긴다. 실제 $n$과 질의 횟수를 측정한다.

## Reference

- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition — Programming Model and Arrays](https://algs4.cs.princeton.edu/11model/)
- Oracle, [The Java Language Specification, Java SE 21 — Array Types](https://docs.oracle.com/javase/specs/jls/se21/html/jls-10.html)
- 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)
- Oracle, [Arrays — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html)