Pattern #8 — Modified Binary Search 🔍

Pattern #8 — Modified Binary Search 🔍

First, a refresher on plain binary search — the fastest way to find something in a sorted list.

1. Plain Binary Search (the base)

   Real-life analogy 📖
   ────────────────────
   Looking up a word in a dictionary. You don't read page 1,
   then 2, then 3. You open the MIDDLE. Too far? Go left half.
   Not far enough? Go right half. Each guess cuts the search
   in HALF. That's why it's O(log n) — blazing fast.

   Find 7 in [1, 3, 5, 7, 9, 11]:
   mid = 5 → 7 > 5 → search right half [7, 9, 11]
   mid = 9 → 7 < 9 → search left half [7]
   mid = 7 → found! ✅

2. The Idea of "MODIFIED" Binary Search

The same halving trick, but the array has a twist — it's rotated, or infinite, or you're looking for a boundary instead of an exact value.

   Binary search isn't just "find X in a sorted array".
   It's "any time you can HALVE the search space by asking a
   yes/no question, you can binary search."

3. Common Variations (a picture)

   A) ROTATED SORTED ARRAY
   ────────────────────────
   [4, 5, 6, 7, 0, 1, 2]   ← sorted, then rotated
                ↑ the "break" point

   One half is always still sorted. Figure out which half is
   sorted, check if your target is in it, and search that half.

   B) FIND THE BOUNDARY ("first/last position")
   ────────────────────────────────────────────
   [1, 2, 2, 2, 3]  → first index of 2? last index of 2?
   Don't stop at the first match — keep halving toward the edge.

   C) SEARCH ON THE ANSWER ("min capacity to ship in D days")
   ────────────────────────────────────────────────────────
   Binary search over POSSIBLE ANSWERS, not array indices. 🤯

4. 🔍 How to SPOT This Pattern

   Use Modified Binary Search when you see:
   ✅ "SORTED array" + "search / find"
   ✅ "rotated sorted array"
   ✅ "first / last / smallest / largest that satisfies X"
   ✅ "minimum / maximum ... such that a condition holds"
   ✅ An O(n) scan works but they want O(log n).

5. The Code Template 📝

   // The safe binary-search skeleton
   function binarySearch(nums, target) {
     let lo = 0, hi = nums.length - 1;
     while (lo <= hi) {
       const mid = lo + Math.floor((hi - lo) / 2);   // avoids overflow
       if (nums[mid] === target) return mid;
       if (nums[mid] < target) lo = mid + 1;   // go right
       else hi = mid - 1;                       // go left
     }
     return -1;
   }

   // Search in a ROTATED sorted array
   function searchRotated(nums, target) {
     let lo = 0, hi = nums.length - 1;
     while (lo <= hi) {
       const mid = lo + Math.floor((hi - lo) / 2);
       if (nums[mid] === target) return mid;
       if (nums[lo] <= nums[mid]) {             // left half is sorted
         if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
         else lo = mid + 1;
       } else {                                 // right half is sorted
         if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
         else hi = mid - 1;
       }
     }
     return -1;
   }

6. Practice Problems

   ⭐ core
   • Binary Search (plain)
   • First Bad Version
   • Search Insert Position

   ⭐⭐ Medium
   • Search in Rotated Sorted Array
   • Find First and Last Position of Element
   • Find Minimum in Rotated Sorted Array
   • Koko Eating Bananas (search on the answer!)

7. ⚠️ Common Mistake

   ❌ `mid = (lo + hi) / 2` can overflow in some languages.
      Use `mid = lo + (hi - lo) / 2`.
   ❌ Infinite loop from wrong `lo`/`hi` updates. Always move a
      pointer PAST mid: `lo = mid + 1` or `hi = mid - 1`.

Key Takeaway

   Modified Binary Search = the halving trick applied to twisted
   inputs (rotated arrays, boundaries) or even to the space of
   possible answers. If you can ask a yes/no question that cuts
   the options in half, you can binary search. O(log n).

Next: Pattern #9 — Subsets, how to generate all combinations of things. 🎛️