코테에서 자주 나오는 유형의 이분탐색이다.
이분탐색은 정렬된 배열에서 특정 값을 찾는 일이고 후보를 한번 탐색할때마다 1/2로 줄여가는 알고리즘이다.
해당 영상을 보고 쉽게 이해할 수 있다.
1654 문제는 이분탐색을 사용하여 특정값이 아닌 범위중 최댓값, 최솟값을 찾는 유형이다.
이분탐색을 그대로 이용하면서 ans 값을 추가하여 범위에 포함될때마다 ans값을 최신화 해주면된다.
반복문의 조건을 s < e 인 경우
1 1
100
의 반례가 존재한다. 즉, 처음부터 e인 지점이 정답일 경우 s가 e에 도달하기 전에 반복문이 끝난다. (실제 디버깅을 통해 확인해보면 이해하기 쉽다)
따라서 s <= e를 통해 s가 e가 될때까지 루프를 진행해야한다.
while (s <= e){
long mid =(s+e)/2;
// now 에 대해 계산
int result = 0;
for (long lan : lanLine){
result += (lan/mid);
}
// 길이가 너무 짧음
if (result >= n){
ans = mid;
s = mid+1;
}
// 길이가 너무 김
else{
e = mid-1;
}
}