Binary search

• 이진탐색은 배열의 특정값을 찾기 위해서 사용
• 순차 탐색에 탐색 속도가 빠른 장점이 있음 -> $O(log_2(N))$
• 하지만 탐색 하려는 배열이 미리 오름차순이나 내림차순으로 정렬이 되어있어야 사용이 가능하다는 단점이 있음

Binary search 예시

• BOJ 2512

• 해당 문제는 각 국가의 예산을 배정 하는 문제로 아래의 조건을 만족해야 함

  1. 모든 신청 금액의 합이 상한치를 넘지 않는 경우에는 희망한 금액만큼 지급
  2. 신청 금액이 상한치를 넘게 되는 경우 상한선을 지정, 상한치 보다 금액이 큰 경우에는 상한액 만큼만 지급한다.

• 구현 방법

  • 0부터 가장 큰 신청액 까지 간격이 1인 상한액 리스트 생성
  • 상한액 리스트의 크기가 1이 될때까지 이진 탐색을 진행하여 결과값 추출
  • 결과값 출력

• 예시

  상한액 : 485
  신청인원 : 4
  신청 금액 : 120, 110, 140, 150
  
  
  
  
  총 9번의 탐색으로 결과 값을 추출 가능

• 코드 구현

import sys

Money_list = []

N = int(sys.stdin.readline())
Money_list = list(map(int,sys.stdin.readline().strip().split(" ")))
Money_list = Money_list[0:N]     
temp_lst = [0 for x in range(max(Money_list))]

Monwy_limit = int(sys.stdin.readline())

USL_money_lst = [x for x in range(max(Money_list)+1)]

while(len(USL_money_lst)>1):
    budget_sum = 0
    start = 0
    mid = len(USL_money_lst)//2
    end = len(USL_money_lst)
    temp_usl = USL_money_lst[mid]

    for i in range(N):
        budget_sum += min(Money_list[i],temp_usl) 
        # min 함수를 이용하여 신청액과 상한액을 비교하여 작은값을 추출

    if budget_sum > Monwy_limit:
        USL_money_lst= USL_money_lst[start:mid]
        continue
    else:
        USL_money_lst= USL_money_lst[mid:end]
        continue

print(USL_money_lst[0])