Jaewoo Song

Categories

• Tech

Binary search is a powerful method to find the desired value in a sorted sequence, but I have not been used to decide whether the given case should be solved with Binary search.

Not only finding value in an array of a vector but also detecting a case in a certain range can be solved with Binary search.

I think I couldn’t catch it due to the lack of experience.

https://www.acmicpc.net/problem/14452

While solving this problem, finding the time $t$ according to each $k$ was done but I got time-out when I tried to find minimum $k$ by reducing $k$ continuously from the state of $k=N$.

In conclusion, the problem was that $k$ is decreased by one.

It is clear that as $k$ becomes bigger, the time $t$ becomes smaller so with the binary search we can find the minimum $k$ faster.

while(1) {
if (start >= end) {
k = start;
break;
}

int mid = (start + end) / 2;

int t = getT(mid);

if (t > T_max) {
start = mid + 1;
} else {
end = mid;
}
}


Although due to some minor exception handling issues I couldn’t get “correct” at once, I could solve this eventually.