탐색의 개념

탐색(searching)은 데이터 모음에서 원하는 값이나 조건을 만족하는 위치를 찾는 일입니다. "이 값이 있는가", "있다면 어디에 있는가", "이 값보다 크거나 같은 첫 원소는 무엇인가" 같은 질문이 모두 탐색입니다. 이 장에서는 선형 탐색과 이진 탐색, 그리고 이진 탐색을 넓힌 매개 변수 탐색(답을 이분 탐색), 삼분 탐색, 해시 조회를 한눈에 정리하고 앞으로 쓸 용어를 맞춥니다.

선형 탐색

선형 탐색(linear search, 순차 탐색)은 앞에서부터 하나씩 비교하는 가장 단순한 방법입니다. 데이터가 정렬되어 있지 않아도 되고, 연결 리스트나 스트림처럼 앞에서부터만 읽을 수 있는 자료에도 쓸 수 있습니다. 대신 최악의 경우 모든 원소를 봐야 하므로 시간이 원소 수 n에 비례합니다.

def linear_search(items, target):
    for i, value in enumerate(items):
        if value == target:
            return i
    return -1


print(linear_search([7, 3, 9, 3], 3))   # 1 (처음 나온 위치)
print(linear_search([7, 3, 9, 3], 4))   # -1

Python의 x in list와 list.index(x)도 내부적으로는 선형 탐색입니다. 원소가 수십 개 정도라면 이것으로 충분하고, 정렬이나 색인을 만드는 비용이 오히려 더 큽니다.

이진 탐색

이진 탐색(binary search)은 정렬된 배열에서 가운데 원소와 비교해 절반을 버리는 일을 반복합니다. 한 번 비교할 때마다 후보 구간이 절반으로 줄어들기 때문에 100만 개 원소에서도 약 20번이면 끝납니다. 핵심 전제는 "정렬되어 있다", 더 일반적으로는 "어떤 지점을 기준으로 조건의 참·거짓이 한 번만 바뀐다"는 단조성입니다.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1          # 닫힌 구간 [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


print(binary_search([2, 5, 8, 12, 16, 23], 16))   # 4

이 형태는 값이 있는지만 알려 줍니다. 같은 값이 여러 개일 때 어느 위치를 돌려줄지 정해져 있지 않다는 점을 기억해 두세요. 실무에서는 다음 절의 lower_bound·upper_bound 꼴이 더 자주 쓰입니다.

경계 찾기: lower_bound와 upper_bound

• lower_bound(x): a[i] >= x를 만족하는 첫 인덱스. 없으면 len(a).
• upper_bound(x): a[i] > x를 만족하는 첫 인덱스. 없으면 len(a).
• 두 값의 차이 upper_bound(x) - lower_bound(x)는 x가 나타나는 개수입니다.
• lower_bound(x)는 정렬을 깨지 않고 x를 끼워 넣을 수 있는 가장 왼쪽 자리이기도 합니다.

Python 표준 라이브러리의 bisect 모듈이 바로 이 두 함수를 제공합니다. bisect_left가 lower_bound, bisect_right가 upper_bound입니다.

from bisect import bisect_left, bisect_right

scores = [10, 20, 20, 20, 35, 50]
print(bisect_left(scores, 20))    # 1
print(bisect_right(scores, 20))   # 4
print(bisect_right(scores, 20) - bisect_left(scores, 20))   # 3개
print(bisect_left(scores, 99))    # 6 (끝)

단조 조건과 답을 이분 탐색

이진 탐색은 배열에만 쓰는 기술이 아닙니다. 정수 범위에서 조건 P(k)가 어떤 경계 앞에서는 모두 거짓이고 그 뒤로는 모두 참이라면(False, False, …, True, True), 처음으로 참이 되는 k를 이진 탐색으로 찾을 수 있습니다. 이것을 매개 변수 탐색(parametric search) 또는 "답을 이분 탐색한다"고 부릅니다. "하루 처리량이 얼마 이상이면 마감 안에 끝나는가" 같은 최적화 문제를 "이 값으로 가능한가"라는 예/아니오 질문으로 바꾸는 것이 요령입니다.

삼분 탐색(ternary search)은 값이 한 번 올라갔다가 내려가는(단봉, unimodal) 함수에서 최댓값이나 최솟값의 위치를 찾습니다. 구간을 셋으로 나눠 두 점의 함숫값을 비교하고 필요 없는 쪽 3분의 1을 버립니다.

해시 조회

해시 테이블(Python의 set·dict)은 키를 해시 값으로 바꿔 바로 그 자리를 찾아가므로 평균 O(1)에 "있는가"를 답합니다. 대신 순서 정보가 없어서 "x 이상인 첫 값", "범위 [a, b]에 든 값" 같은 질문에는 답하지 못합니다. 정확히 같은 키만 찾는다면 해시, 순서나 범위가 필요하면 정렬 + 이진 탐색이 기본 선택입니다.

용어 정리

정리

• 정렬되지 않은 작은 데이터에는 선형 탐색이 가장 간단합니다.
• 정렬된 데이터에는 이진 탐색이 O(log n)으로 빠르며, 경계를 찾는 lower_bound·upper_bound 꼴이 가장 쓸모 있습니다.
• 단조 조건만 있으면 배열이 없어도 답 자체를 이진 탐색할 수 있습니다.
• 정확한 일치만 필요하면 해시, 순서·범위 질의가 필요하면 정렬 + 이진 탐색을 고릅니다.