[알고리즘] 이진탐색 (Binary Search) 파이썬 구현

자료 출처: https://youtu.be/94RC-DsGMLo

1. 이진탐색이란?

정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방식으로 동작하는 알고리즘

• 시작점, 끝점, 중간점을 이용한다.
• 시간 복잡도: O(logN)

재귀 또는 반복문을 이용하여 구현할 수 있다. 이하는 재귀를 이용하여 푸는 법.

# 재귀 방식으로 구현

def binary_search(arr, target, start, end):
    if start > end:
        return None

    mid = (start + end) // 2
    
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, end)
    else:
        return binary_search(arr, target, start, mid - 1)

이어서 반복문으로 푸는 방법도 알아보자.

# 반복문 이용하여 구현

def binary_search(arr, target, start, end):

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
            
    return None

2. 파이썬 이진 탐색 라이브러리 bisect

• bisect_left(arr, x): 정렬된 순서를 유지하며 배열 arr에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(arr, x): 정렬된 순서를 유지하며 배열 arr에 x를 삽입할 가장 오른쪽 인덱스를 반환

from bisect import bisect_left, bisect_right

arr = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(arr, x))
print(bisect_right(arr, x))

# 2
# 4

bisect 라이브러리를 활용하여 값이 특정 범위에 속하는 데이터의 개수를 쉽게 구할 수도 있다.

def count_by_range(arr, left_val, right_val):
    right_index = bisect_right(arr, right_val)
    left_index = bisect_left(arr, left_val)
    return right_index - left_index

3. 파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제(yes or no)로 바꾸어 해결하는 기법으로, 일반적으로 이진 탐색으로 풀 수 있다.

• 조건의 만족 여부(yes or no)에 따라 탐색 범위를 좁혀서 해결할 수 있다.
• 큰 탐색 범위를 보면 이진탐색을 떠올릴 수 있어야 한다.