📌 이진 탐색
🤔 원리
1. 왼쪽 기준값과 오른쪽 기준값을 정한다.
2. 그 두 값의 중간값을 구한다.
3. 찾고자 하는 값의 위치를 파악한다.
3-1. 찾는 값이 중간값보다 왼쪽에 위치하는 경우 : 왼쪽 기준값은 유지, 오른쪽 기준값을 기존 중간값으로 갱신
3-2. 찾는 값이 중간값보다 오른쪽에 위치하는 경우 : 왼쪽 기준값을 기존 중간값으로 갱신, 오른쪽 기준값은 유지
4. 지정한 종료 시점까지 해당 프로세스를 반복한다.
🤔 장점
처음부터 끝까지 탐색하는 브루트포스 알고리즘과 다르게, 탐색 범위를 크게 줄일 수 있다.
🤔 단점
탐색 대상 데이터가 정렬되어 있어야 한다.
⚙️ 이진 탐색 구현 예시
k, n = map(int, input().split())
had = []
for i in range(k):
had.append(int(input()))
left = 1 # 왼쪽 기준값
right = max(had) # 오른쪽 기준값
while left <= right: # 탐색 종료 조건
mid = (left + right) // 2 # 중간값 계산
cnt = sum([k // mid for k in had]) # 탐색 대상 값
if cnt >= n: # 탐색 대상의 위치 파악
left = mid + 1 # 왼쪽 기준점을 갱신
else:
right = mid - 1 # 오른쪽 기준점을 갱신
print(right)