복잡도

탐색 방법을 고를 때는 한 번 찾는 데 드는 시간뿐 아니라 데이터를 준비하는 비용, 갱신 비용, 메모리, 그리고 어떤 종류의 질문에 답할 수 있는지를 함께 따져야 합니다. 이 장에서는 선형 탐색, 이진 탐색, 매개 변수 탐색, 삼분 탐색, 해시 조회의 비용을 정리하고 언제 무엇을 고를지 기준을 세웁니다.

선형 탐색

• 최선: 첫 원소가 답이면 비교 1번, O(1).
• 평균: 찾는 값이 고르게 있다면 약 n / 2번, O(n).
• 최악: 끝에 있거나 없으면 n번, O(n).
• 공간: 추가 메모리 O(1).

준비 비용이 없고 정렬되지 않은 자료에도 쓸 수 있다는 것이 장점입니다. 캐시 친화적으로 연속된 메모리를 차례로 읽기 때문에, 원소가 수십 개 이하라면 실제로는 이진 탐색보다 빠른 경우도 많습니다.

이진 탐색

비교할 때마다 구간이 절반이 되므로 최악의 비교 횟수는 floor(log2 n) + 1입니다. 원소 100만 개면 20번, 10억 개면 30번입니다.

• 시간: 최선 O(1)(가운데에서 바로 찾는 닫힌 구간 꼴), 평균·최악 O(log n). lower_bound 꼴은 항상 log n 근처를 돕니다.
• 공간: 반복문 구현은 O(1), 재귀 구현은 호출 스택 때문에 O(log n).
• 전제: 정렬되어 있어야 하며, 정렬 자체는 O(n log n)입니다.

비교 횟수를 직접 세어 보면 로그 증가가 눈에 보입니다.

def lower_bound_count(a, x):
    lo, hi, steps = 0, len(a), 0
    while lo < hi:
        steps += 1
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, steps


for n in (10, 1_000, 1_000_000):
    a = list(range(n))
    print(n, lower_bound_count(a, n - 1)[1])   # 3, 10, 20

정렬 비용은 언제 회수되는가

질의가 k번 있을 때 선형 탐색은 k * n, 정렬 후 이진 탐색은 n log n + k log n이 듭니다. 질의가 log n번보다 훨씬 많다면 정렬해 두는 쪽이 이깁니다. 반대로 한두 번만 찾고 버릴 데이터라면 정렬하지 않는 편이 낫습니다.

정렬된 배열에 원소를 넣거나 지우는 일은 뒤쪽 원소를 밀어야 해서 O(n)입니다. 삽입과 삭제가 잦다면 균형 이진 탐색 트리나 B-트리, 또는 Python의 sortedcontainers 같은 자료 구조가 탐색과 갱신을 모두 O(log n) 근처로 맞춰 줍니다.

매개 변수 탐색과 삼분 탐색

답의 범위 크기가 R이고 조건 검사 한 번에 C가 든다면 매개 변수 탐색은 O(C * log R)입니다. 예를 들어 배열 전체를 훑어 가능 여부를 판단하는 조건이면 O(n log R)입니다. 실수 범위라면 원하는 정밀도 eps에 대해 log2(R / eps)번 반복하거나, 간단히 100번처럼 고정 횟수를 돌립니다.

삼분 탐색은 한 번에 구간이 3분의 2로 줄고 매번 함수를 두 번 계산합니다. 따라서 같은 정밀도에 이진 탐색보다 함수 계산이 더 많이 듭니다. 정수 범위에서 이웃 비교 이진 탐색으로 바꿀 수 있다면 그쪽이 효율적입니다.

import math

R, eps = 1e9, 1e-6
print(math.ceil(math.log2(R / eps)))            # 이진: 약 50번 반복, 계산 50번
print(math.ceil(math.log(R / eps, 1.5)) * 2)    # 삼분: 약 86번 반복, 계산 약 172번

해시 조회

해시 테이블은 평균 O(1)로 키를 찾지만 모든 키가 같은 칸에 몰리면 최악 O(n)이 될 수 있습니다. 메모리도 배열보다 많이 쓰고, 순서가 없어서 범위 질의, 다음으로 큰 값, k번째 값 같은 질문에는 답하지 못합니다.

import random
import timeit
from bisect import bisect_left

data = sorted(random.sample(range(10_000_000), 100_000))
as_set = set(data)
probe = data[len(data) // 2]

print(timeit.timeit(lambda: probe in data, number=200))     # 선형: 가장 느림
print(timeit.timeit(lambda: bisect_left(data, probe), number=200))
print(timeit.timeit(lambda: probe in as_set, number=200))   # 해시: 가장 빠름

실행 환경마다 숫자는 다르지만, 원소 10만 개에서는 대개 선형 탐색이 나머지 둘보다 수천 배 이상 느립니다.

비교표

표의 k는 범위에 든 결과 개수입니다.

정리

• 선형 탐색은 O(n)이지만 준비 비용이 없어 작은 데이터와 일회성 탐색에 알맞습니다.
• 이진 탐색은 O(log n)이며 정렬 비용 O(n log n)은 질의가 많을 때 회수됩니다.
• 매개 변수 탐색은 O(조건 검사 비용 * log 범위), 삼분 탐색은 같은 정밀도에 함수 계산이 더 듭니다.
• 정확한 일치만 필요하면 해시, 범위나 순서가 필요하면 정렬 배열이나 트리를 고릅니다.