DSA Notes

Techniques

Binary Search on the Answer

Guess the answer, then check whether it is feasible.

The idea

When a problem asks for the largest or smallest value that satisfies a condition, try turning it around: for a given value, can the condition be met? That check is usually a simple greedy pass.

If feasibility is monotone (when d works, everything smaller works too), binary-search the value. The cost is O(check × log range).

Phrases that signal it: “maximise the minimum”, “minimise the maximum”, “the least time / capacity needed”.

Sample problem

1552. Magnetic Force Between Two Balls ↗ Medium

There are baskets at given positions and m balls. Put each ball in a basket so that the smallest distance between any two balls is as large as possible. Return that distance.

position = [1,2,3,4,7], m = 3
output = 3   (balls at 1, 4, 7)

Why the solution works

Choosing the baskets directly is hard. Checking a given distance d is easy: go left to right and greedily place a ball whenever the basket is at least d from the previous ball. If m balls fit, d is feasible.

Feasibility is monotone: if d works, every smaller d works. So the answers form “yes … yes, no … no”, and binary search finds the last yes.

This is the pattern behind “maximise the minimum”: search the answer, verify with a greedy pass.

Complexity: O(n log n) to sort, plus O(n log(range)) for the search. O(1) extra memory.

Watch out

  • Convince yourself the check is monotone before coding; otherwise binary search returns nonsense.
  • The bounds must contain the answer: start from the widest sensible range.
  • Sums inside the check often overflow int.
Watch it run

Try your own input

Practise on LeetCode