Binary Search

정렬된 배열에서 특정 값을 빠르게 찾는 탐색 알고리즘

1. 배열의 가운데 값(Pivot)을 기준으로 찾고자 하는 값과 비교한다.
2. 찾고자 하는 값이 가운데 값보다 작으면 왼쪽 부분 배열을 탐색한다.
3. 크다면 오른쪽 부분 배열을 탐색한다.
4. 이 과정을 반복하여 값을 찾거나 배열의 크기가 0이 될 때까지 진행한다.

특징

• 시간 복잡도: O(logn) (탐색 범위가 절반씩 줄어듦)
• 공간 복잡도: O(1) (반복문 구현 시), O(logn) (재귀 구현 시)
• 선형 탐색(Linear Search)의 O(n)보다 훨씬 빠름
• 단점: 배열이 반드시 정렬되어 있어야 함

# Iterative
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  # 찾지 못한 경우

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
print(binary_search(arr, target))

# Recursive
def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
print(binary_search_recursive(arr, target, 0, len(arr) - 1))

파이썬 라이브러리

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

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

  

from bisect import bisect_left, bisect_right

def count_by_range(arr, leftVal, rightVal):
    right = bisect_right(arr, rightVal)
    left = bisect_left(arr,leftVal)
    return right-left

arr= [1,2,3,3,3,3,4,4,8,9]
# 3의 개수를 구함
print(count_by_range(arr,3,3))

Parametric Search

특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

이진 탐색을 이용해서 해결한다.

EX) 떡 자르기