자료구조 · 알고리즘 기초집LESSON 14

이진 탐색: 정렬된 데이터에서 빠르게 찾기

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

14강. 이진 탐색: 정렬된 데이터에서 빠르게 찾기

1. 이번 강의에서 해결할 문제

점수 목록이 커질수록 원하는 점수를 처음부터 찾는 선형 탐색 비용이 늘어납니다. 정렬 비용을 이미 지불한 데이터에서는 범위를 절반씩 줄일 수 있습니다.

2. 학습 목표

3. 핵심 개념

이진 탐색은 정렬된 구간의 중간값과 목표를 비교해 탐색 범위를 절반으로 줄입니다. 중복 중 아무 위치가 아니라 첫 위치가 필요하면 lower bound, 즉 목표 이상이 처음 나타나는 위치를 찾습니다. 탐색 전 정렬이 필요하며, 한 번만 찾는다면 정렬 O(n log n)이 선형 탐색 O(n)보다 비쌀 수 있습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/BinaryScoreSearch.java

src/BinaryScoreSearch.java
import java.util.Arrays;

public class BinaryScoreSearch {
    static int lowerBound(int[] sorted, int target) {
        int low = 0, high = sorted.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (sorted[mid] < target) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] scores = {700, 900, 900, 1200, 1500};
        int index = lowerBound(scores, 900);
        System.out.println("첫 900 위치: " + index);
        int missing = lowerBound(scores, 1000);
        System.out.println("1000 삽입 위치: " + missing);
        System.out.println(Arrays.toString(scores));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/BinaryScoreSearch.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/BinaryScoreSearch.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\BinaryScoreSearch.java
java -cp .\out BinaryScoreSearch

예상 결과: 첫 900 위치 1과 1000의 삽입 위치 3이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

탐색 구간 [low, high)에는 아직 답 후보가 남아 있습니다. 중간값이 목표보다 작으면 답이 오른쪽에만 있고, 그렇지 않으면 mid도 첫 위치 후보라 high를 mid로 옮깁니다. 매번 구간이 절반이 되어 시간 O(log n), 반복 구현의 추가 공간 O(1)입니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ