[Python] 이진 탐색 알고리즘 구현하기

 

 

💡 선형 탐색보단 이진 탐색을!

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53] 16개의 데이터

 

선형 탐색 O(n)
순서대로 하나씩 탐색, 정렬된/정렬되지 않은 리스트 모두 사용 가능, 데이터가 큰 경우 성능 저하

• 최선의 경우 - 1개의 값만 확인 (2를 찾을 때)
• 최악의 경우 - 16개의 값 확인 (없는 숫자를 찾을 때)

이진 탐색 O(lg n)
반으로 범위를 줄여가며 중앙값을 탐색, 정렬된 리스트에서만 사용 가능, 데이터가 큰 경우 뛰어난 성능 보임

• 최선의 경우 - 중앙의 1개의 값만 확인 (19를 찾을 때)
• 최악의 경우 - 4개의 값 확인 (없는 숫자를 찾을 때)

 

👀 데이터가 커질수록 성능 차이가 극명해진다.

128개의 데이터 ➡️ 선형 탐색 - 128번 확인, 이진 탐색 - 7번 확인

30억개의 데이터 ➡️ 선형 탐색 - 30억번 확인, 이진 탐색 - 31번 확인

 

선형 탐색

def binary_search(target, data):
    if target in data: return data.index(target)

print(binary_search(2, [2, 3, 5, 7, 11])) # 0
print(binary_search(0, [2, 3, 5, 7, 11])) # None
print(binary_search(5, [2, 3, 5, 7, 11])) # 2
print(binary_search(3, [2, 3, 5, 7, 11])) # 1
print(binary_search(11, [2, 3, 5, 7, 11])) # 4

 

이진 탐색

def binary_search(target, data):
    left_idx, right_idx = 0, len(data) - 1
    
    while left_idx <= right_idx:
        mid_idx = (left_idx + right_idx) // 2 # 중앙 인덱스 구하기
        mid_element = data[mid_idx] # 중앙값
        
        if target == mid_element:
            return mid_idx
        elif target < mid_element: # 타겟이 중앙값보다 작다면 오른쪽 범위를 버린다.
            right_idx = mid_idx - 1
        elif target > mid_element: # 타겟이 중앙값보다 크다면 왼쪽 범위를 버린다.
            left_idx = mid_idx + 1