검색 알고리즘 (Search Algorithms) — 선형 탐색과 이진 탐색 파이썬 구현

 

검색 알고리즘 (Search Algorithms) — 선형 탐색과 이진 탐색 파이썬 구현

 

검색 알고리즘은 데이터 집합에서 원하는 값을 빠르게 찾기 위해 사용되는 핵심 개념이다. 특히 코딩 테스트나 실무 개발에서 자주 등장하는 기본 탐색 기법은 선형 탐색(Linear Search)과 이진 탐색(Binary Search)이다. 이 글에서는 두 알고리즘의 원리, 시간 복잡도, 장단점, 그리고 파이썬 구현 코드를 함께 정리한다.

---

검색 알고리즘이란?

검색 알고리즘(Search Algorithm)은 데이터 구조 안에서 특정한 값(또는 조건을 만족하는 값)을 찾는 절차를 의미한다.

대표적인 탐색 방법에는 다음과 같은 것들이 있다.

• 선형 탐색 (Linear Search)
• 이진 탐색 (Binary Search)
• 깊이 우선 탐색 (DFS)
• 너비 우선 탐색 (BFS)

이번 글에서는 선형 탐색과 이진 탐색을 중점적으로 다룬다.

---

선형 탐색 (Linear Search)

동작 원리

• 리스트의 처음부터 끝까지 순차적으로 탐색한다.
• 목표 값을 찾으면 인덱스를 반환하고, 끝까지 못 찾으면 실패로 처리한다.

시간 복잡도

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

파이썬 코드 예시

from typing import Iterable, Any, Optional

def linear_search(arr: Iterable[Any], target: Any) -> Optional[int]:
    for idx, val in enumerate(arr):
        if val == target:
            return idx
    return None

---

이진 탐색 (Binary Search)

동작 원리

• 정렬된 배열에서만 사용 가능하다.
• 중간 인덱스를 선택해 목표 값과 비교한다.
  • 목표 < 중간값 → 왼쪽 탐색
  • 목표 > 중간값 → 오른쪽 탐색
  • 목표 == 중간값 → 인덱스 반환
• 탐색 범위를 절반으로 줄여가며 반복한다.

시간 복잡도

• 최악/평균: 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]:
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return None

 

파이썬 코드 예시 (재귀)

def binary_search_rec(arr, target, lo=0, hi=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)

---

선형 탐색 vs 이진 탐색 비교

구분	선형 탐색	이진 탐색
전제 조건	없음	정렬 필요
시간 복잡도	O(n)	O(log n)
구현 난이도	매우 간단	조금 더 복잡
데이터 크기	작을 때 유리	클 때 유리
사용 사례	간단한 검색	빠른 검색, 빈번한 탐색

 

---

결론 및 활용

• 작은 데이터 → 선형 탐색이 더 직관적이고 단순하다.
• 큰 데이터 & 탐색 빈번 → 이진 탐색을 사용해야 효율적이다.
• 실무에서는 파이썬의 bisect 모듈을 사용하면 안전하고 빠르게 이진 탐색을 구현할 수 있다.

---

마무리

검색 알고리즘은 데이터 구조와 알고리즘 학습의 기본이다.

• 선형 탐색은 가장 단순하지만 효율은 떨어진다.
• 이진 탐색은 정렬된 배열에서 강력한 성능을 발휘한다.

두 알고리즘을 이해하고 직접 구현해보는 것은 코딩 테스트 준비와 실제 프로젝트 개발 모두에 큰 도움이 된다.