Jaewoo Song
Jaewoo Song


  • 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.


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;

  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.