알고리즘 BinarySearch 정리

---

코딩 테스트를 위한 알고리즘 정리글

Binary Search

사용 시점

시간이 오래걸리는 문제, 효율성 해결
이분 탐색하여 문제를 풀 수 있을 경우 사용

Binary Search 기본 사용법

일반적으로 이렇게 했고, 문제에 따라서 유동적으로 적용해야함

min값	0 또는 구할 수 있는 최소값(이것보다 더 적게는 안나온다 하는 값)
max값	해당 타입의 최대값(Integer.MAX_VALUE 등) 혹은 구할 수 있는 최대값
min값	(max+min)/2
while 문 조건식	min <= max
while 문 내부 반복문	mid값 케이스가 성공하면 max=mid-1 mid값 케이스가 실패하면 min=mid+1
return	대부분 min값

Programmers 이분탐색: 입국 심사 링크

입력값	n	입국심사를 기다리는 사람
	times	심사관이 한 사람을 검사하는데 걸리는 시간
출력값	long	모든 사람이 심사를 받는데 걸리는 시간

min값

0

max값

(times 배열 중 가장 큰 값) × n

접근 방향

• max값일때 항상 성공 → mid일 때에도 성공?
• mid일 때 성공(>=n) → mid보다 작을때에도 성공? → max = half-1
• mid일 때 실패(<n) → mid보다 커야함 → min = mid+1

생각할 점

성공/실패 구분 포인트

• times[i]/mid → i번째 입국 심사관이 mid시간동안 처리할 수 있는 사람의 수와 n 비교

생각할 점

• max값이 long범위보다 클 수 있음 → BigInteger 사용