Join waitlist
DSACommunity question

how to know when to use binary search on answer

Asked by Aditya Verma 27 days ago 2 answers 10 votes

Koko eating bananas, ship packages in D days etc. I understand the solution after seeing it but I never recognise these in a new problem

2 answers

Karthik Rajan27 days agoMost voted9

Ask two things:
1. If I guess an answer X, can I check if X works in O(n)?
2. If X works, does every bigger X also work (or every smaller)?

If both yes, binary search over X.

Usually the question says something like "minimum possible maximum" or "smallest X such that".

Practise: koko, ship packages, split array largest sum, aggressive cows, book allocation.

Tushar Goyal25 days ago2

aggressive cows came in my college's amazon OA last year

Related questions

Go deeper

Want the full explanation, not just an answer?

Structured lessons on DSA, core CS, Java and interview skills, each ending in a quiz so you know it stuck.