검색 알고리즘 비교: O(n) vs. O(log n) — 개발자를 위한 실무 가이드
백만 개 이상의 요소를 갖는 배열에서 선형 탐색은 최대 1,000만 번의 연산이 필요할 수 있지만, 이진 탐색은 단 24번의 비교로 끝납니다. 본 글에서는 파이썬으로 구현한 4가지 검색 알고리즘을 깊이 있게 분석합니다: 시간 복잡도, 실제 적용 시 고려해야 할 장단점, 그리고 상황별 선택 기준. 오버플로우 안전한 구현, lower_bound/upper_bound, LeetCode 문제 풀이에 바로 활용 가능한 예제까지 모두 포함했습니다.
검색 문제 정의: 배열 arr에서 target 값의 인덱스를 찾거나, 존재하지 않으면 -1을 반환합니다. 배열은 정렬되어 있을 수도 있고 아닐 수도 있으며, 고정된 데이터일 수도, 실시간으로 변하는 동적 데이터일 수도 있습니다. 실제 사례로는 전자상거래의 SKU 조회(수백만 개 SKU), 핀테크 거래 ID 검증 등이 있습니다.
정렬되지 않은 데이터에 적합한 선형 탐색
모든 종류의 컬렉션에서 작동합니다. 요소를 순차적으로 하나씩 확인합니다.
구현 코드:
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1복잡도:
- 시간: 최악/평균 경우 O(n), 최선 경우 O(1).
- 공간: O(1).
이진 탐색과 그 변형 알고리즘
정렬된 배열에서만 사용 가능합니다. 탐색 범위를 반복적으로 절반으로 줄여나갑니다.
반복문 기반 구현: 정수 오버플로우 방지를 위해 mid = left + (right - left) // 2 방식을 사용하세요. C++/Java에서는 필수적이며, 파이썬에서도 안정성과 관행 측면에서 권장됩니다.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def lower_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
def upper_bound(arr, target):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
# 예시
sorted_arr = [1, 3, 3, 5, 7, 9]
print(binary_search(sorted_arr, 5)) # 3
print(lower_bound(sorted_arr, 3)) # 1
print(upper_bound(sorted_arr, 3)) # 3복잡도: 시간 O(log n), 공간 O(1).
lower_bound는 target을 삽입할 수 있는 가장 왼쪽 위치를 반환하며, upper_bound는 가장 오른쪽 위치를 반환합니다. 중복 값 처리 및 LeetCode 문제 "정렬된 배열에서 원소의 첫 번째와 마지막 위치 찾기" 해결에 반드시 필요한 개념입니다.
스트리밍 또는 크기를 모르는 데이터에 적합한 지수 탐색
길이를 미리 알 수 없는 정렬된 배열, 혹은 target이 배열 앞부분에 집중되어 있을 가능성이 높은 경우에 최적입니다. 먼저 지수적 증가로 탐색 범위를 좁힌 후, 이진 탐색을 적용합니다.
def exponential_search(arr, target):
if not arr:
return -1
if arr[0] == target:
return 0
bound = 1
while bound < len(arr) and arr[bound] < target:
bound *= 2
left = bound // 2
right = min(bound, len(arr) - 1)
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 예시
big_arr = list(range(1_000_000))
print(exponential_search(big_arr, 123456)) # 123456복잡도: 평균 O(log i) — 여기서 i는 target의 인덱스, 최악의 경우 O(log n), 공간 O(1).
동적 컬렉션에 적합한 해시 기반 탐색
해시 테이블(set/dict)을 이용해 평균 O(1)의 탐색 속도를 제공합니다.
def hash_search_set(arr, target):
s = set(arr)
return target in s
def hash_search_dict(pairs, key):
d = dict(pairs)
return d.get(key)
# 예시
nums = [10, 20, 30, 40]
print(hash_search_set(nums, 30)) # True
pairs = [("a", 1), ("b", 2)]
print(hash_search_dict(pairs, "b")) # 2복잡도: 평균 O(1), 최악의 경우 O(n) (해시 충돌 발생 시), 공간 O(n).
알고리즘 선택 가이드라인
- 정렬되지 않은 배열: 요소 수가 100개 미만이거나 탐색 빈도가 낮을 때는 선형 탐색.
- 정렬된 고정 데이터: 이진 탐색.
- 삽입이 잦은 동적 데이터: 순서가 중요하지 않다면 해시 테이블.
- 스트리밍 또는 크기를 모를 때: 지수 탐색.
| 알고리즘 | 평균 시간 | 최악 시간 | 공간 | 요구 조건 |
|-----------|-----------|------------|-------|--------------|
| 선형 탐색 | O(n) | O(n) | O(1) | 없음 |
| 이진 탐색 | O(log n) | O(log n) | O(1) | 정렬됨 |
| 지수 탐색 | O(log i) | O(log n) | O(1) | 정렬됨 |
| 해시 탐색 | O(1) | O(n) | O(n) | 해시 가능 키 |
핵심 요약
- 1,000만 개 요소에서 이진 탐색은 약 24번의 비교만으로 끝나지만, 선형 탐색은 최대 1,000만 번이 필요합니다.
- 이진 탐색에서
mid계산 시 항상 오버플로우 안전한 방식(left + (right - left) // 2)을 사용하세요. 파이썬이라도 견고한 코딩 습관입니다. - 해시 테이블은 메모리(O(n))를 희생해 평균 O(1)의 초고속 탐색을 얻습니다.
lower_bound와upper_bound는 중복 처리 및 삽입 로직 구현에 필수적인 도구입니다.- 지수 탐색은 대규모 정렬 배열에서 타겟이 앞부분에 몰려 있을 때 특히 뛰어난 성능을 보입니다.
— Editorial Team
아직 댓글이 없습니다.