[파이썬] 바이너리 서치 (이진 탐색)

바이너리 서치에 대해서 알아간다.

탐색 범위를 절반씩 줄여가면서 찾아간다.

바이너리 서치의 대상은 정렬되어 있어야 한다.

 

시간 복잡도 : O(logn)

 

Binary Search vs Sequential Search (From www.penjee.com)

 

코드를 보면 확실하다

 

 

바이너리 서치 구현

def binary_search(nums, target):
    left = 0
    right = len(nums)
    while left < right:
        pivot = (left + right) // 2

        if nums[pivot] == target:
            return pivot
        elif nums[pivot] < target:
            left = pivot + 1
        else:
            right = pivot

    return -1

# 이진 탐색 대상은 정렬되어 있어야 함
nums = [1, 3, 5, 7, 9, 10, 15, 20, 25]


target = 20
idx = binary_search(nums, target)
print(f'타겟 : {target}, 위치 : {idx}')

target = 999
idx = binary_search(nums, target)
print(f'타겟 : {target}, 위치 : {idx}')

'''
Output:

타겟 : 20, 위치 : 7
타겟 : 20, 위치 : -1
'''

피봇을 설정하고 탐색 범위(left, right)를 계속 반으로 줄여가면서 탐색해나간다.

 

 

바이너리 서치 구현(재귀 함수 사용)

def binary_search_recur(nums, target, left, right):
    if left >= right:
        return -1

    pivot = (left + right) // 2
    if nums[pivot] == target:
        return pivot
    elif nums[pivot] < target:
        left = pivot + 1
    else:
        right = pivot

    return binary_search_recur(nums, target, left, right)

# 이진 탐색 대상은 정렬되어 있어야 함
nums = [1, 3, 5, 7, 9, 10, 15, 20, 25]

left = 0
right = len(nums)

target = 20
idx = binary_search_recur(nums, target, left, right)
print(f'타겟 : {target}, 위치 : {idx}')

target = 999
idx = binary_search_recur(nums, target, left, right)
print(f'타겟 : {target}, 위치 : {idx}')

'''
Output:

타겟 : 20, 위치 : 7
타겟 : 20, 위치 : -1
'''

 

바이너리 서치를 정리하자면,

• 시간 복잡도 O(logN)
• 탐색 대상은 정렬되어 있어야 함
• 탐색 대상을 범위를 반으로 나누어 가면서 탐색
• 탐색 시간이 굉장히 짧음