선형 탐색: 정렬 없이 첫 답을 보장하는 Java 순차 스캔

정렬되지 않은 배열에서 값 하나를 찾으려면 “앞에서부터 본다”가 정답일 수 있다. 선형 탐색은 느린 알고리즘의 대명사가 아니라, 사전 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 프로그램이다.

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");
    }
}

javac --release 21 LinearSearchDemo.java
java LinearSearchDemo

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

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
Oracle, The Java Language Specification, Java SE 21 — Array Types
Oracle, The Java Virtual Machine Specification, Java SE 21 — Frames and Heap
Oracle, Arrays — Java SE 21 API