Binary Search

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

배열의 가운데 값(Pivot)을 기준으로 찾고자 하는 값과 비교한다.

찾고자 하는 값이 가운데 값보다 작으면 왼쪽 부분 배열을 탐색한다.

크다면 오른쪽 부분 배열을 탐색한다.

이 과정을 반복하여 값을 찾거나 배열의 크기가 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))
Python
복사

파이썬 라이브러리

•

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))

Python
복사

Parametric Search

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

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

EX) 떡 자르기

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm
만큼의 길이를 가져갑니다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이 의 최댓값을 구하는 프로그램을 작성해라.

적절한 높이를 찾을때까지 이진탐색을 수행하면서 H를 조절한다.

조건의 만족 여부에 따라서 탐색 범위를 좁혀가면서 해결한다.

중간점의 값이 시간이 지날수록 최적화된 값이 된다

n, m = list(map(int,input().split(' ')))

array = list(map(int,input().split()))

start = 0
end = max(array)

result = 0
while(start <=end):
    total = 0
    mid = (start+ end)//2
    for x in array:
        if x>mid:
            total += x-mid
    #기준미달인 경우 더 많이 자르기
    if total < m:
        end = mid-1
    #기준을 충족하는 경우 더 적게 자르는 쪽으로
    else: 
        result = mid
        start = mid+1

print(result)
        
Python
복사