Binary Search and Explicit Boundaries

Binary search discards half a candidate interval using a monotonic predicate or sorted order. Correctness follows the maintained interval invariant.

Before you start

You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.

The practical goal is to reason through this situation: Search the first position satisfying a predicate using a half-open interval. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.

Step-by-step walkthrough

Step 1: Use one interval convention

Maintain a half-open candidate range [low, high).

Step 2: Make every iteration progress

False moves low past mid; true can retain mid as a candidate.

Step 3: Return the transition boundary

Low equals high when no candidate interval remains.

Worked scenario

Search the first position satisfying a predicate using a half-open interval.

function firstTrue(n, predicate) {
  let low = 0, high = n;
  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (predicate(mid)) high = mid;
    else low = mid + 1;
  }
  return low;
}

The predicate must be false-then-true. Returning n means no true position exists.

Common mistake

Changing endpoint conventions midway creates missing candidates or infinite loops.

Verify the behavior

Test n=0, all false, all true and every possible transition in a small array.

Interview exercise

Test boundary behavior.

Answer and reasoning

Cover empty input, all-false, all-true and a transition at each end, verifying progress on every iteration.

Continue learning

Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.