Revision: Binary Search

This is a quick revision sheet for Binary Search DSA pattern.
👉 Here is the link to the OG full-length post Binary Search Pattern – The Interviewer's Favorite

Use this page for last-minute interview prep, fast memory refresh, or revisiting key templates and pitfalls.

---

✅ When to Use Binary Search

• Array is sorted
• Problem asks to find/insert/search a value
• Decision space is monotonic (e.g. if X works, X+1 works too)
• Problem wants to minimize/maximize a number under constraints → Use Binary Search on Answer
• Precision answer needed (like square root) → Use Decimal Binary Search

---

🧠 5 Must-Know Binary Search Templates

1. Classic Search (while (left <= right)) → For finding exact value in a sorted array

2. Insert Position / Lower Bound (while (left < right)) → First element ≥ target

3. First/Last Position → Two-pass binary search for [first, last] indices

4. Binary Search on Answer → No array; search over range [min, max]
   → Use isValid(mid) to simulate

5. Decimal Precision Search → Loop ~100 times to get accurate float value
   → Used for square roots, min speed with floating-point limits

---

⚠️ Pitfalls to Avoid

• ❌ Don’t write left = mid or right = mid
• ✅ Always shrink window: left = mid + 1 or right = mid - 1
• Loop bugs = Your range isn't shrinking
• Know when to use left < right vs. left <= right

---

🧪 Binary Search on Answer – How to Think

“If I guess this number, can I make it work?”

• true → It’s feasible → try smaller → right = mid
• false → It’s not enough → try bigger → left = mid + 1

Use isValid(mid) to simulate the guess (e.g. can Koko finish bananas at this speed?).

---

📎 Always Dry Run These Edge Cases

• Empty array
• Single-element array
• Target not found
• Target at edges (first or last)
• Duplicates (for left/right bounds)
• Even vs. odd length inputs

---

🧠 Want a full walkthrough with code, dry runs, and examples?
👉 Read the full Binary Search Deep Dive here →