Skip to content

Binary Search on Monotone Boundaries

Problem

When you see "search boundary", monotone predicate, sorted array, or "first/last bad/true position"

Strategy: Binary Search on Monotone Boundaries

  • Think about this
    • This is binary search on answer or boundary, not value lookup.
    • Maintain an interval that is guaranteed to contain the answer.
    • Typical monotone split:
      • all false then all true
      • smaller works, larger fails
  • Avoid this
    • Do not use linear search when the statement gives monotonicity.
    • Do not lose the boundary candidate by moving the wrong side.
    • Do not use vague loop conditions that hide off-by-one mistakes.
  • Tell this to the interviewer
    • State the invariant on [left, right].
    • Prefer the standard form:
      • while left < right
      • shrink toward first true
  • See these problems