Half-open invariant, lower-bound, upper-bound, search-on-answer.

Binary Search — One Template, Every Variant

Binary search halves the search space each iteration — O(log n) on a sorted collection. The half-open invariant [low, high) makes every variant consistent: low is inclusive, high is exclusive. Lower-bound finds the first position ≥ target; upper-bound finds the first position > target. Binary search on the answer solves monotonic problems by searching over a solution space rather than an array.

Interactive Pipeline Flow

UnderstandImplementOptimise

📊 Sorted Input — or monotone predicate

Input must be sorted (for array search) or the predicate must be monotone: false...false...true...true (for search-on-answer).

Architecture Diagrams

Same template, different predicates for each binary search variant.

Loading diagram...

Key Design Decisions

🚫Never (low+high)/2

For large indices, low+high overflows int. Always use low + (high-low)/2.

📐One template for all variants

The half-open [low,high) invariant with "if pred: high=mid; else: low=mid+1" works for every binary search variant. Memorise one pattern.

🎯Search-on-answer for optimisation problems

"Find minimum speed to deliver packages in D days" → binary search over speed values with a canDeliver(speed) predicate.

Discussion