What is binary search on the answer, and when do you reach for it?
It is a way of solving problems where the answer is a number, where you can check whether a number works, and where a bigger number always fails once a smaller one has failed.
So the pattern is this. You work out the smallest number and the biggest number that could be the answer. Then you take the middle one and check whether it is good enough. If it is good then you move the high bound down, because you know a smaller answer might also work. If it is not good then you move the low bound up, because a smaller answer cannot work either.
def min_capacity(trips):
low, high = 1, sum(trips)
while low < high:
mid = (low + high) // 2
if can_carry(trips, mid):
high = mid
else:
low = mid + 1
return low
So when do you reach for it? When all three of these are true. The answer is a single number. You can write a function that says whether a given number works. And the check has to be in one direction, so that if a number does not work then every smaller number does not work either.
the problem the answer the check
-------------------------- ----------------- ---------------------
least boats for the trips how many boats can the boats carry it?
smallest square root the number is the square big enough?
least speed for a journey how fast does it arrive in time?
fewest cuts for the pieces how many cuts are there enough pieces?
So what makes it different from ordinary binary search? In ordinary binary search you look for a value that is in a list. In binary search on the answer there is no list. You make up the list of possible answers, which is usually the whole range of numbers from the smallest to the biggest, and then you search that range in the same way.
And that is why the bounds matter so much. The low bound has to be a number that might be the answer, and the high bound has to be a number that is guaranteed to work. If the high bound is too small then the search can miss the answer, and if the low bound is too big then it can miss it as well.
And the complexity is O of log r for the time, where r is the size of the range of numbers, and O of 1 for the space. So if the answer is somewhere between 1 and a billion then it takes about thirty checks, no matter how big the original data is.
The last question in this topic shows the simplest possible example of it.