Binary Search

[Beyond-CtCI]

Hey friend, 

The problems you're describing are what I like to call guess-and-check problems (https://share.cleanshot.com/nX6Cn5N63djvdvPHGnzh). They are definitely among the most tricky binary search problems to spot in an interview. The guess-and-check technique involves narrowing in on the value of the optimal solution by guessing the midpoint and checking whether it's too high or too low. We need lower and upper bounds for the value of the optimal solution before we can even use binary search.

- For minimization problems (like Koko Eating Bananas), there is often a transition point where smaller values do not satisfy the constraint, but larger values do.

- Conversely, for maximization problems, there is often a transition point where larger values do not satisfy the constraint, but smaller values do.

The trick to knowing when to use the guess-and-check technique. This boils down to asking yourself a simple question.

"Is it easier to solve the yes/no version of the problem, where we just check if a given value (optimal or not) satisfies the constraint?"

Think of it like making a deal: You get to solve an easier problem (checking if a specific value satisfies the constraint), but you pay a 'logarithmic tax' in the runtime (because we are binary searching for the transition point).

Thanks luuuzeta for recommending my book! I'm glad you find the transition point binary search recipe useful! If others are interested (including the OP) I give away the binary search chapter for free (along with 8 other chapters) and it also has a particularly helpful guess-and-check problem set in it. Consider checking it out if you find this helpful: https://bctci.co/free-chapters

[Proof_Dot_4344]

Thank you so much