Binary search on the answer

When the array is not sorted but the answer space is - the pattern most candidates never see.

13 min read · Lesson 5 of 6 · Pro

The pattern

Normal binary search hunts for a value in a sorted array. This pattern searches something else entirely: the range of possible answers.

It applies when the question has this shape:

The answer is a number in a known range, say 1 to 10^9.
You can write a function feasible(x) that returns true or false.
feasible is monotonic: once it becomes true it stays true as x

increases (or the mirror image).

If those hold, the answers look like false false false TRUE true true, and binary search finds the boundary in O(log range) calls to feasible.

Recognise it from: minimum such that, maximum such that, smallest speed / capacity / size that still works.

The rest of this lesson is Pro

The free lessons of DSA Interview Patterns finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.