[Algorithm 개념] binary search (이진 탐색)

탐색 알고리즘에는 크게 1. 이진 탐색 2. BFS 3. DFS가 있다. 이번 챕터에서는 이진 탐색에 관해 알아볼 것다. 

이진 탐색

• 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 차근히 확인하는 방법.
• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.

재귀문 구현

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    #찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    
    else:
        return binary_search(array, target, mid+1, end)

반복문 구현

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid

        elif array[mid] > target:
            end = mid - 1

        else:
            start = mid + 1
        
    return None

 

파이썬 이진 탐색 라이브러리

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

from bisect import bisect_left, bisect_right

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

print(bisect_left(a, x))
print(bisect_right(a, x))

 

파라메트릭 서치 (Parametric Search)

파라메트릭 서치란 최적화 문제를 결정 문제 ('예' 혹은 '아니오')로 바꾸어 해결하는 기법. (e.g. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제)

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다. 

 

문제 1. 떡볶이 떡 만들기 

• 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단 합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다.
• 예를들어 높이가 19, 14, 10, 17 cm 떡이 나란히 있고 절단기 높이를 15cm 로 지정하면 자른 뒤 떡의 높이는 4, 0, 0, 2 cm 가 될것입니다. 총 6cm 떡을 가져갈 수 있음.

#n = 떡의 갯수, m = 요청한 떡의 길이
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)

 

문제 2. 정렬된 배열에서 특정 수의 갯수 구하기

• N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있음. 이때 이 수열에서 x가 등장하는 횟수를 계산. 수열 {1,1,2,2,2,2,3}이 있을 때 x=2라면, 현재 수열에서 값이 원소가 4개이므로 4개 출력.

# solution : python 내부 lib인 bisect 사용. 특정값이 등장하는 첫 번째 위치와 마지막 위치를 찾아 차이를 계산해 문제를 해결할 수 있다.

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index
    
    
n, x = map(int, input().split())
array = list(map(int, input().split())) #전체 데이터 입력

#이진탐색
count = count_by_range(array, x, x)

if count == 0:
    print(-1)
    
# 값이 x인 원소가 존재하면
else:
    print(count)