Typorithm · hard

Binary Search on Answer

binary-search-on-answerpatternsfeasibilityoptimization

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Binary Search on Answer

Basic Patterns

Binary search the answer space using a yes/no feasibility test.

Some problems ask for a minimum speed, capacity, or distance instead of an index.

If feasibility is monotonic — once true, always true for bigger values — the answer space can be halved.

The loop converges on the boundary: the smallest candidate where canDo flips to true.

Search candidates, not array positions.

canDo must be monotonic.

Feasible keeps mid; infeasible drops it.

function minFeasible(low, high, canDo) {
  while (low < high) {
    const mid = Math.floor((low + high) / 2);

    if (canDo(mid)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Answer range

low and high bracket candidate answers, not array indexes.

while (low < high)

2. Candidate answer

Try the middle candidate between the current bounds.

const mid = Math.floor((low + high) / 2)

3. Feasibility check

canDo answers: does this candidate satisfy the constraint?

if (canDo(mid))

4. Keep feasible

mid works, but something smaller might too — keep mid in range.

high = mid

5. Drop infeasible

mid fails, so every answer ≤ mid fails too.

low = mid + 1

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.