← dsa.gleee.in
DSA · 02

Binary Search & Search on Answer

Google Interview Cheat Sheet — Binary Search & Monotonic Predicates

O(log N) · O(N log(AnswerRange))

1. Pattern Recognition Triggers

  • Sorted or Rotated Array: At every midpoint, at least one half is guaranteed sorted.
  • "Minimize the Maximum" / "Maximize the Minimum": Classic Search on Answer trigger (e.g., Split Array, Koko, Ship Packages).
  • Monotonic Predicate: Ask "If X works, does X+1 also work?" → produces F F F T T T.

2. Universal First-True (F F F T T T) Template

var lo = minAns
var hi = maxAns
while (lo < hi) {
    val mid = lo + (hi - lo) / 2
    if (feasible(mid)) {
        hi = mid       // keep mid, search left
    } else {
        lo = mid + 1   // discard mid, search right
    }
}
return lo // converges to first True!

3. Classic Interview Traps

  • Integer Overflow: Never write (lo + hi) / 2—always use lo + (hi - lo) / 2.
  • Infinite Loop: With floor-mid, setting lo = mid hangs when hi == lo + 1. Always advance lo = mid + 1 (or use ceil-mid for Last-True).
  • Inclusive Bounds: Check if hi starts at maxAns (inclusive) and maintain lo < hi.
◉ Rotated Sorted Array · [4, 5, 6, 7, 0, 1, 2], target = 0
SEARCHING
Step 1 / 4
{ } SearchRotatedArray.kt
Idiomatic Kotlin
◆ Step Explanation & Invariant
Step 1 / 4

Loading...

Invariant Time: O(log N) · Space: O(1)
Shortcuts: ← / → Step · Space Play/Pause · R Reset