7-2. 이진탐색 문제

1. 떡볶이 떡 만들기 문제

정답 코드

#떡의 개수(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 #최대한 덜 잘랐을 때가 정답이므로, 여기서 result 기록
        start = mid +1

print(result)

문제2. 정렬된 배열에서 특정 수의 개수 구하기(이진탐색으로 , 선형탐색x)

bisect 라이브러리를 이용한 파이썬 코드

from bisect import bisect_left,bisect_right

#값이 [left_value,right_value]인 데이터 개수를 반환하는 함수
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)