DSA: Binary Search on Boundaries

Walk through how you'd use binary search to find a boundary — the first true value in a sorted boolean array — and all the edge cases.

Technical Reference & Key Concepts

The Challenge: First True

Given a sorted boolean array (all false then all true), find the index of the first true. No such index if none exists. Explain your approach out loud, then handle the edges.

Core questions to address:

  1. What is the invariant, and what does the loop condition guarantee?
  2. What are ALL the edge cases (all false, all true, single element) and what does each return?
  3. What is the complexity, and when would linear scan be fine?