[python] 코딩테스트 대비 - 이분검색(일직선에 배치)

문제)

답안 코드)

import sys
#sys.stdin=open("input.txt", "r")
def Count(len):#len으로 배치 할 수 있는 마리수 리턴
    cnt=1#마리 수
    ep=Line[0]#최근에 말을 배치한 우;ㅊ;
    for i in range(1, n):
        if Line[i]-ep>=len:#배치 할 수 있다면,
            cnt+=1 #마리수 증가
            ep=Line[i] #끝지점 변경
    return cnt
 
n, c=map(int, input().split())
Line=[]
for _ in range(n):
    tmp=int(input())
    Line.append(tmp)
Line.sort()#정렬
lt=1#왼쪽 포인터
rt=Line[n-1]#오른쪽 포인터# 1~amx(Line)에서 답을 찾음
while lt<=rt:
    mid=(lt+rt)//2#중간값
    if Count(mid)>=c:#답으로 가능하다면
        res=mid#답에 넣고,
        lt=mid+1#더 큰 답이 있는지 탐색
    else:#불가능하다면,
        rt=mid-1#mid가 너무 큰것.
 
print(res)