이진 탐색(Binary Search), 선형 탐색보다 얼마나 빠를까?

탐색SearchSearchSearch이란?

탐색은 데이터 속에서 원하는 값을 찾는 작업입니다.
예를 들어, [1, 3, 5, 7, 9] 안에서 5가 있는지 찾는 것입니다.

탐색 알고리즘에는 대표적으로 두 가지가 있습니다

• 선형 탐색 $Linear Search$
• 이진 탐색 $Binary Search$

---

선형 탐색

def linear_search(arr, target):
	for i in range(len(arr)):
    	if arr[i] == target:
        	return i
    return -1

• 방식: 앞에서부터 하나씩 비교
• 정렬 필요 없음
• 시간복잡도: O$n$ $최악의 경우 끝까지 가야 함$

---

이진 탐색

• 전제 조건: 데이터가 정렬되어 있어야 함

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

• 방식: 중간값과 비교 → 절반식 줄여가면 탐색
• 정렬된 배열에서만 사용 가능
• 시간복잡도: O$log n$

---

실행 속도 직접 비교해보기

import time

arr = list(range(1, 1_000_001))  # 1부터 100만까지
target = 999_999

# 선형 탐색
start = time.time()
linear_search(arr, target)
end = time.time()
print(f"Linear Search: {end - start:.6f} sec")

# 이진 탐색
start = time.time()
binary_search(arr, target)
end = time.time()
print(f"Binary Search: {end - start:.6f} sec")

# Linear Search: 0.080123 sec
# Binary Search: 0.000013 sec

 

---

탐색 횟수 예시	선형 탐색 $O(n$)	이진 탐색 $O(log n$)
n = 10	최대 10회	최대 4회
n = 1,000	최대 1,000회	최대 10회
n = 1,000,000	최대 1,000,000회	최대 20회

 

이진 탐색은 한 번 비교할 때마다 탐색 범위가 절반으로 줄어들기 때문입니다.

---

주의할 점

• 이진 탐색은 정렬된 배열에서만 사용 가능
• 정렬되지 않은 배열에서는 먼저 정렬 O$n log n$ → 이득이 없을 수도 있음
• 인덱스가 중요한 경우$위치 반환$에는 이진 탐색을 직접 구현해야 함

---

항목	선형 탐색	이진 탐색
사용 조건	정렬 필요 없음	정렬 필요
시간복잡도	O$n$	O$log n$
속도	느림	매우 빠름
코드 구현	쉬움	비교적 복