Search Algorithms — 선형 탐색과 이진 탐색 (Python 구현 포함)

데이터 집합에서 원하는 값을 빠르고 정확하게 찾는 방법을 다룬다. 이 글에서는 선형 탐색(Linear Search) 과 이진 탐색(Binary Search) 의 개념, 시간 복잡도, 파이썬 구현, 그리고 실전에서의 선택 기준을 정리한다.

1) 탐색 알고리즘 한눈에 보기

• 선형 탐색: 처음부터 끝까지 차례대로 비교한다. 정렬 여부와 무관하게 사용할 수 있으나 최악의 경우 모든 원소를 확인한다.
• 이진 탐색: 정렬된 배열에서 탐색 구간을 절반으로 줄여가며 찾는다. 매우 빠르지만 정렬되어 있어야 한다는 전제가 필요하다.

알고리즘	전제 조건	평균/최악 시간 복잡도	공간 복잡도
선형 탐색	없음	O(n) / O(n)	O(1)
이진 탐색	정렬 필요	O(log n) / O(log n)	O(1) (반복), O(log n) (재귀 콜스택)

---

2) 선형 탐색 (Linear Search)

동작 원리

리스트의 첫 번째 원소부터 마지막 원소까지 순서대로 비교한다. 목표값을 찾으면 해당 인덱스를 반환하고, 끝까지 못 찾으면 실패를 의미하는 값을 반환한다.

시간 복잡도

• 평균/최악: O(n)
• 공간: O(1)

파이썬 구현

from typing import Iterable, Any, Optional

def linear_search(arr: Iterable[Any], target: Any) -> Optional[int]:
    '''
    선형 탐색: arr 에서 target 을 앞에서부터 찾고, 있으면 인덱스를 반환한다.
    없으면 None 을 반환한다.
    '''
    # 리스트가 아닌 Iterable 도 지원하기 위해 enumerate 사용
    for idx, val in enumerate(arr):
        if val == target:
            return idx
    return None

---

3) 이진 탐색 (Binary Search)

동작 원리

정렬된 배열에서 mid 인덱스를 잡아 목표값과 비교한다.

• 목표 < arr[mid] 이면 오른쪽 절반을 버리고 왼쪽을 탐색
• 목표 > arr[mid] 이면 왼쪽 절반을 버리고 오른쪽을 탐색
• 같으면 인덱스 반환

시간 복잡도

• 평균/최악: O(log n)
• 공간: O(1) (반복), O(log n) (재귀)

주의: 반드시 정렬된 배열이어야 한다.

파이썬 구현 (반복적)

from typing import Sequence, Any, Optional

def binary_search_iter(arr: Sequence[Any], target: Any) -> Optional[int]:
    '''
    이진 탐색 (반복): 정렬된 arr 에서 target 의 인덱스를 찾는다.
    없으면 None 을 반환한다.
    '''
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2  # 오버플로우 걱정 없음 (파이썬 int 무한정 확장)
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return None

파이썬 구현 (재귀적)

def binary_search_rec(arr: Sequence[Any], target: Any, lo: int = 0, hi: Optional[int] = None) -> Optional[int]:
    '''
    이진 탐색 (재귀): 정렬된 arr 에서 target 인덱스를 찾는다.
    없으면 None 을 반환한다.
    '''
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return None

    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

응용: 중복 원소에서의 첫/마지막 위치 (lower/upper bound)

이진 탐색을 살짝 변형하면 중복 원소가 있을 때 첫 번째 등장 인덱스(lower bound)와 마지막 등장 인덱스(upper bound)를 구할 수 있다.

from typing import Sequence, Any, Optional, Tuple

def lower_bound(arr: Sequence[Any], target: Any) -> int:
    '''
    정렬된 arr 에서 target 이상이 처음 나타나는 인덱스(삽입 위치)를 반환한다.
    target 이 arr 에 없다면, target 을 유지하는 정렬 상태에서 들어갈 수 있는 가장 왼쪽 인덱스를 반환한다.
    '''
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # 0..len(arr)

def upper_bound(arr: Sequence[Any], target: Any) -> int:
    '''
    정렬된 arr 에서 target 을 초과하는 값이 처음 나타나는 인덱스(삽입 위치)를 반환한다.
    '''
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def find_first_last(arr: Sequence[Any], target: Any) -> Tuple[Optional[int], Optional[int]]:
    '''
    정렬된 arr 에서 target 의 첫 번째/마지막 인덱스를 (first, last) 로 반환한다.
    target 이 없으면 (None, None) 을 반환한다.
    '''
    left = lower_bound(arr, target)
    if left == len(arr) or arr[left] != target:
        return None, None

    right = upper_bound(arr, target) - 1
    return left, right

---

4) 언제 어떤 탐색을 쓸까

• 데이터가 작거나 정렬 비용이 아까운 경우: 선형 탐색이 단순하고 구현이 빠르다.
• 탐색을 자주 하고 데이터가 크며 정렬 상태를 유지할 수 있는 경우: 이진 탐색이 압도적으로 유리하다.
• 중복 원소 처리/범위 질의: lower_bound / upper_bound 변형으로 첫/마지막 위치, 구간 길이 등을 빠르게 계산할 수 있다.
• 실전 팁
  • 이진 탐색 전 정렬 보장을 확인한다.
  • 인덱스 범위(lo <= hi)와 중간 인덱스 계산, 경계 업데이트(lo = mid + 1, hi = mid - 1)를 헷갈리지 않도록 주석을 남긴다.
  • 표준 라이브러리를 활용할 수 있으면 bisect 모듈을 고려한다. (동일한 동작을 안전하게 제공한다)

---

5) 테스트 코드 모음

아래 스니펫을 그대로 실행하면 각 함수가 의도대로 동작하는지 빠르게 확인할 수 있다.

def _run_tests():
    # 선형 탐색
    arr1 = [42, 7, 13, 7, 99]
    assert linear_search(arr1, 42) == 0
    assert linear_search(arr1, 7) == 1  # 첫 등장 반환
    assert linear_search(arr1, 100) is None

    # 이진 탐색 (반복/재귀)
    arr2 = [1, 3, 3, 3, 5, 7, 9]
    assert binary_search_iter(arr2, 1) == 0
    assert binary_search_iter(arr2, 3) in (1, 2, 3)  # 중복 중 하나
    assert binary_search_iter(arr2, 4) is None

    assert binary_search_rec(arr2, 9) == 6
    assert binary_search_rec(arr2, 2) is None

    # lower/upper bound + first/last
    assert lower_bound(arr2, 3) == 1
    assert upper_bound(arr2, 3) == 4
    assert find_first_last(arr2, 3) == (1, 3)
    assert find_first_last(arr2, 4) == (None, None)

    print("All tests passed!")

if __name__ == "__main__":
    _run_tests()

---

마무리

• 선형 탐색은 어디서나 쉽게 쓸 수 있는 기본기다.
• 이진 탐색은 정렬된 데이터에서 빛을 발한다. 탐색이 잦고 데이터가 크다면 반드시 고려해야 한다.
• 실전에서는 표준 라이브러리(bisect)와 함께 경계 탐색(lower/upper bound) 패턴을 함께 익혀두면 문제 풀이와 서비스 코드 모두에서 유용하다.