[Algorithm] 이진 탐색 알고리즘

이진 탐색이란?

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
(이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다)

다른 탐색으로는 순차탐색이 있고 순차탐색은 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인한다.

이진 탐색 소스코드

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

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

    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
    
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다")
else:
    print(result + 1)
    

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

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

bisect 라이브러리를 이용한 범위 내 데이터 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, l_v, r_v):
    r_i = bisect_right(a, r_v)
    l_i = bisect_left(a, l_v)
    return r_i - l_i

a = [1,2,3,3,3,3,4,4,8,9]

print(count_by_range(a, 4, 4)) # 2
print(count_by_range(a, -1, 3)) # 6

파라메트릭 서치

• 최적화 문제를 결정문제 (예, 아니오) 로 바꾸어 해결하는 기법
  -> 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 코딩테스트에서 파라메트릭 서치 문제는 이진탐색을 이용하여 해결할 수 있다.

이진 탐색 예제 1 <떡볶이 떡 만들기> (파라메트릭 서치)

• 동빈이는 떡집일을 한다. 떡볶이 떡을 만들어야 하는데 떡의 길이가 모두 일정치가 않다. 대신에 한 봉지에 들어가는 떡의 총 길이는 절단기로 맞춰준다. 절단기에 높이(h)를 지정하면 줄지어진 떡을 한 번에 절단한다. h보다 긴 떡은 윗 부분이 잘리고, 낮은 떡은 잘리지 않는다. 예를들어 높이가 19,14,10,17cm인 떡이 있고 절단기 높이가 15cm라면 자른 떡의 높이는 15,14,10,15cm가 되고 잘린 떡의 길이는 4,0,0,2cm이다. 손님은 6cm만 가져간다. 손님이 왔을 때 요청한 총 길이가 m일때 적어도 m만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하라.

m, n = 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
    // 현재 떡의 길이 x
    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라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력한다.

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()) # 데이터의 개수 N, 찾고자하는 값 X 입력받기
array = list(map(int, input().split()) # 전체데이터 입력받기
# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

if count == 0:
    print(-1)
else:
    print(count)