algo · 02

이진 탐색

알고리즘탐색이진 탐색

이진 탐색(Binary Search)은 정렬된 데이터에서 탐색 범위를 매번 절반씩 줄여나가며 원하는 값을 찾는 알고리즘입니다. 배열을 처음부터 하나씩 확인하는 선형 탐색과 달리, 가운데 값과 비교해 한쪽 절반을 통째로 버리기 때문에 훨씬 적은 횟수로 답을 찾습니다.

핵심 개념

전제 조건: 정렬

이진 탐색은 데이터가 정렬되어 있어야만 동작합니다. 정렬되어 있지 않으면 "가운데 값보다 크면 오른쪽에 있다"는 판단 자체가 성립하지 않습니다.

핵심 개념

low / mid / high 포인터

탐색 범위의 시작(low)과 끝(high), 그리고 그 가운데(mid)를 가리키는 세 포인터로 현재 탐색 범위를 표현합니다.

핵심 개념

한 번의 비교, 절반 제거

target과 arr[mid]를 비교해 크면 왼쪽 절반을, 작으면 오른쪽 절반을 통째로 버립니다. 한 번 비교할 때마다 남은 범위가 절반으로 줄어듭니다.

핵심 개념

시간복잡도: O(log n)

범위가 매번 절반이 되므로, n개에서 1개가 남을 때까지 절반씩 나누는 횟수는 log₂n번입니다. 이전 토픽(시간/공간 복잡도)에서 본 로그 시간이 바로 이것입니다.

핵심 개념

선형 탐색과의 차이

선형 탐색은 하나씩 확인하므로 최악의 경우 n번 비교(O(n))가 필요합니다. 같은 16개 배열에서도 이진 탐색은 최대 5번, 선형 탐색은 최대 16번까지 걸릴 수 있습니다.

핵심 개념

반복 vs 재귀 구현

이진 탐색은 반복문(while)으로도, 재귀 호출로도 구현할 수 있습니다. 두 방식 모두 매 단계 범위를 절반으로 줄인다는 원리는 동일합니다.

왜 정렬이 먼저 필요한가 — 데이터가 정렬되어 있지 않다면 이진 탐색을 쓰기 전에 먼저 정렬(ds-09 정렬 알고리즘)해야 합니다. 정렬 자체에 O(n log n)이 들지만, 같은 데이터를 여러 번 탐색해야 한다면 한 번 정렬해두는 것이 이득일 수 있습니다.

mid 계산 시 주의할 점 — mid = (low + high) / 2로 계산할 때, low와 high가 매우 큰 값이면 정수 오버플로가 발생할 수 있습니다. low + (high - low) / 2 형태로 계산하면 이를 방지할 수 있습니다.

못 찾는 경우 — low가 high보다 커지면(low > high) 더 이상 탐색할 범위가 없다는 뜻이므로 target이 배열에 없다고 판단하고 탐색을 종료합니다.

실전에서의 의미 — n=1,000,000개짜리 정렬된 데이터에서도 이진 탐색은 약 20번만 비교하면 됩니다. 데이터가 클수록 선형 탐색과의 격차는 상상 이상으로 벌어집니다 — "선형 탐색과 비교" 탭에서 직접 확인해보세요.

이진 탐색의 역사와 어려움

이진 탐색의 아이디어는 단순하지만 오류 없이 구현하기는 의외로 어렵습니다. 조슈아 블로크(Joshua Bloch)의 구글 블로그 글은 이진 탐색이 1946년에 처음 발표되었고 버그 없는 구현은 1962년에야 나왔다고 소개합니다. 같은 글에서 자바 표준 라이브러리의 이진 탐색에도 오래도록 오버플로 버그가 있었다고 설명합니다.

숫자로 확인하기

최대 탐색 단계 수 — n개에서 최악의 경우 ⌊log₂ n⌋ + 1단계를 거칩니다(한 단계에 한 번 비교하는 구현 기준). n = 16이면 5번, n = 1,000,000이면 20번, n = 10억(10⁹)이면 30번입니다.

32비트 정수 오버플로 예 — 32비트 부호 있는 정수의 최댓값은 2,147,483,647입니다. low = 1,500,000,000, high = 2,000,000,000이면 low + high = 3,500,000,000이어서 범위를 넘습니다. low + (high − low) / 2는 중간에 이런 큰 값이 생기지 않습니다.

정렬 비용과 손익분기 — 정렬되지 않은 n개를 한 번만 찾으면 선형 탐색 O(n)이, 비교 기반 정렬 O(n log n) 뒤에 이진 탐색을 하는 것보다 쌉니다. 같은 데이터를 여러 번 탐색할수록 정렬을 한 번 해 두는 쪽이 유리해집니다.

자주 하는 오해

정렬만 되어 있으면 어떤 자료구조에서든 O(log n)이다 — 가운데 원소를 O(1)에 읽을 수 있어야 합니다. 연결 리스트는 가운데 노드까지 순회해야 해서, 비교는 O(log n)번이어도 이동 비용이 O(n)이라 선형 탐색보다 빠르지 않습니다.

중복 값이 있으면 첫 번째 위치를 찾아 준다 — 기본 이진 탐색은 같은 값 중 아무 위치나 찾습니다. 자바 문서는 중복이 있으면 어느 것이 찾아질지 보장하지 않는다고 설명합니다. 첫 위치가 필요하면 lower bound 방식으로 따로 구현합니다.

mid 위치를 올림으로 하든 내림으로 하든 상관없다 — 경계를 low = mid처럼 갱신하면서 mid를 내림으로 계산하면 범위가 줄지 않아 무한 루프에 빠질 수 있습니다. 경계 갱신(mid ± 1)과 mid 계산 방식을 함께 맞춰야 합니다.

이진 탐색이 항상 선형 탐색보다 빠르다 — n이 아주 작으면 둘의 차이가 거의 없고, 정렬되어 있지 않은 데이터라면 정렬 비용을 먼저 치러야 합니다.

면접에서 이렇게 물어요

면접 질문

이진 탐색 구현에서 mid를 (low + high) / 2로 구하면 왜 문제가 되나요?

low와 high가 클 때 합이 정수 범위를 넘어 오버플로가 날 수 있습니다. low + (high − low) / 2로 계산하면 합을 만들지 않아 안전합니다.

면접 질문

값이 없을 때 어떻게 알 수 있나요?

low가 high보다 커지면 남은 범위가 없다는 뜻이라 탐색을 끝내고 없다고 판단합니다. 자바의 Arrays.binarySearch는 없을 때 삽입될 위치를 이용해 음수를 돌려줍니다.

면접 질문

정렬된 배열에서 특정 값의 첫 위치나 마지막 위치를 찾으려면 어떻게 하나요?

같은 값을 찾아도 멈추지 않고 범위를 계속 좁히는 lower bound와 upper bound 방식으로 찾습니다. C++의 std::lower_bound는 값보다 작지 않은 첫 원소의 위치를 돌려줍니다.

면접 질문

정렬된 배열이 아닌 문제에도 이진 탐색을 쓸 수 있나요?

답이 되는 값에 대해 '가능하다/불가능하다'가 한 지점에서 바뀌는 문제(단조성이 있는 결정 문제)라면 답의 범위를 이진 탐색할 수 있습니다. 이를 파라메트릭 서치라고 부르기도 합니다.

실제 시스템에서는

Java — Arrays.binarySearch는 정렬된 배열을 전제로 하고, 값이 없으면 삽입 위치를 이용한 음수를 돌려줍니다. 정렬되지 않은 배열에 쓰면 결과가 정해져 있지 않습니다.

Python — 표준 라이브러리 bisect 모듈이 이진 탐색으로 정렬된 리스트에 삽입 위치를 찾는 bisect_left, bisect_right를 제공합니다.

데이터베이스 인덱스 — 정렬된 키를 갖는 B-Tree 인덱스는 이진 탐색과 같은 발상으로 범위를 좁혀 갑니다. 자세한 구조는 인덱스 토픽에서 봅니다.

함께 보면 좋은 토픽

시간·공간 복잡도 — O(log n)이 어떤 증가율인지 숫자로 비교해 봅니다.

정렬 비교 — 이진 탐색의 전제 조건인 정렬 알고리즘을 비교합니다.

투 포인터 — 정렬된 배열을 다루는 또 다른 기법을 봅니다.

배열과 연결 리스트 — 임의 접근이 되는 배열이 이진 탐색에 필요한 이유를 봅니다.

참고 자료

이진 탐색의 버그 — Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken — Google Research

Java Arrays — Arrays — Java SE 21 API

Python bisect — bisect — Array bisection algorithm — Python documentation

Java — 선형 탐색 (비교 기준)

/* ── 처음부터 하나씩 확인 — 정렬 여부와 무관하게 동작 ─────── */
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;   // 찾으면 인덱스 반환
    }
    return -1;                              // 끝까지 못 찾음
}

최악의 경우(target이 맨 끝에 있거나 없을 때) arr.length번, 즉 O(n)만큼 비교해야 합니다.
정렬 여부와 상관없이 항상 동작하지만, 데이터가 이미 정렬되어 있다면 이진 탐색보다 훨씬 비효율적입니다.

Java — 이진 탐색 (반복문)

/* ── 정렬된 배열 전제: 매 단계 범위를 절반으로 좁힘 ────────── */
public int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;   // 오버플로 방지 계산
        if (arr[mid] == target) {
            return mid;                    // 발견
        } else if (arr[mid] < target) {
            low = mid + 1;                 // 오른쪽 절반만 다시 탐색
        } else {
            high = mid - 1;                // 왼쪽 절반만 다시 탐색
        }
    }
    return -1;                              // low > high → 존재하지 않음
}

low <= high인 동안 매 반복마다 범위가 절반으로 줄어들기 때문에, 최악의 경우에도 log₂n번이면 반복이 끝납니다.
n=16이면 최대 4번, n=1,000,000이면 최대 약 20번 — 반복 횟수가 n이 아니라 n의 로그에 비례하는 O(log n) 시간복잡도입니다.

Java — 이진 탐색 (재귀)

/* ── 반복문 대신 재귀 호출로 같은 로직을 표현 ──────────────── */
public int binarySearchRecursive(int[] arr, int target, int low, int high) {
    if (low > high) return -1;             // 기저 사례: 더 볼 범위가 없음

    int mid = low + (high - low) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high);   // 오른쪽 절반 재귀
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1);    // 왼쪽 절반 재귀
    }
}

반복문 버전과 시간복잡도는 동일하게 O(log n)이지만, 매 호출마다 범위가 절반으로 줄어들기 때문에 재귀 호출 깊이도 log₂n에 비례합니다.
ds-10(동적 프로그래밍)에서 다룬 재귀와 달리 매번 부분 문제가 하나뿐이라 중복 계산이 없어, 메모이제이션 같은 별도의 캐시가 필요하지 않습니다.

이진 탐색(Binary Search)이 동작하기 위한 전제 조건은?

가운데 값과 비교해 절반을 버리려면 순서가 있어야 합니다.

이진 탐색은 배열이 정렬되어 있다는 전제하에 중간값과 비교해 탐색 범위를 절반씩 줄여가는 알고리즘입니다.

16개 원소에서 이진 탐색은 최악의 경우 몇 번 비교하나요?

log2(16) = 4입니다.

이진 탐색은 매번 절반씩 줄어들므로 최악의 경우 비교 횟수는 log2(n)에 비례합니다. log2(16)=4이므로 최대 4번이면 충분합니다.

이진 탐색이 선형 탐색보다 빠른 이유는?

O(log n)과 O(n)의 차이입니다.

선형 탐색은 하나씩 순서대로 확인해 O(n)이 걸리지만, 이진 탐색은 정렬된 배열에서 매번 범위를 절반으로 줄여 O(log n)만에 찾습니다.