# Master Binary Search: Templates, Rotated Arrays, Median of Two Sorted Arrays, and Binary Search on Answer Binary search is one of the most elegant and efficient algorithms, yet it hides many traps. Off-by-one errors, infinite loops, and confusing `mid` calculations trip up even experienced developers. Once you understand the underlying **left/right boundary pattern** and how to apply it to rotated arrays, median finding, and **binary search on answer**, you’ll solve a huge family of problems with confidence. In this article, you will: * Learn the universal `lo, hi, mid` **template** for leftmost/rightmost boundaries. * Solve **Search in Rotated Sorted Array** and **Find Minimum in Rotated Sorted Array** in O(log n). * Conquer the legendary **Median of Two Sorted Arrays** in O(log(min(m,n))). * Master **binary search on answer** with **Koko Eating Bananas** and **Capacity To Ship Packages**. * Walk away with a clear mental model. Let’s dive in. * * * ## 1\. The Left/Right Boundary Binary Search Template ### The Classic Exact‑Match Search For a sorted array with no duplicates, a standard binary search looks like this: ```python lo, hi = 0, len(arr) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 ``` But what if the array has duplicates and you need the **first** or **last** occurrence? That’s where the boundary template shines. ### The Core Idea: Finding the First `True` (Left Boundary) Many problems boil down to: *“Find the smallest index where a condition becomes* `True`*.”* We use a `while lo < hi` loop with **lower mid** `mid = (lo + hi) // 2` and update: * If condition at `mid` is **True** → the answer is at `mid` or to the left → `hi = mid`. * If condition at `mid` is **False** → the answer is strictly to the right → `lo = mid + 1`. When the loop exits, `lo == hi` and points to the first `True` index. **Critical**: because we set `hi = mid`, we must use the **floor** mid (i.e. `(lo + hi)//2`) to avoid an infinite loop when `lo` and `hi` differ by 1. Template (first true / leftmost): ```python lo, hi = 0, n - 1 while lo < hi: mid = lo + (hi - lo) // 2 if condition(mid): hi = mid else: lo = mid + 1 return lo # first index where condition is True ``` ### Finding the Last `True` (Right Boundary) If you need the **largest** index where a condition is `True`, the roles reverse. You must use **upper mid** `mid = (lo + hi + 1) // 2` so that when you do `lo = mid` the interval shrinks. If you used the lower mid, `lo = mid` could get stuck. For understanding dry run example where lo and hi are adjacent, i.e. lo=4 and hi=5. Template (last true / rightmost): ```python lo, hi = 0, n - 1 while lo < hi: mid = lo + (hi - lo + 1) // 2 if condition(mid): lo = mid else: hi = mid - 1 return lo # last index where condition is True ``` ### Example: LeetCode 34 – Find First and Last Position of Element in Sorted Array We can directly apply both templates: ```python def searchRange(nums, target): if not nums: return [-1, -1] # leftmost lo, hi = 0, len(nums)-1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] >= target: hi = mid else: lo = mid + 1 left = lo if nums[lo] == target else -1 # rightmost lo, hi = 0, len(nums)-1 while lo < hi: mid = (lo + hi + 1) // 2 if nums[mid] <= target: lo = mid else: hi = mid - 1 right = lo if nums[lo] == target else -1 return [left, right] ``` This template will appear again and again. Now let’s see it in action on more exotic problems. * * * ## 2\. Search in Rotated Sorted Array (LeetCode 33) **Problem**: You are given an array that was originally sorted but then rotated at an unknown pivot. Example: `[4,5,6,7,0,1,2]`, target `0` → return `4`. All values are distinct. Do it in O(log n). ### Key Insight – One‑Pass Binary Search Even though the array isn’t fully sorted, **one half** (either left or right of `mid`) **is always strictly sorted**. By comparing `nums[lo]`, `nums[mid]`, and `target` we can discard one half. **Algorithm**: * Standard `while lo <= hi` loop. * If `nums[mid] == target` → found. * **Check which side is sorted**: * If `nums[lo] <= nums[mid]` → **left half is sorted**. * If `target` lies between `nums[lo]` and `nums[mid]`, go left (`hi = mid - 1`), else go right (`lo = mid + 1`). * Else → **right half is sorted**. * If `target` lies between `nums[mid]` and `nums[hi]`, go right (`lo = mid + 1`), else go left (`hi = mid - 1`). ```python def search(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid # left part is sorted if nums[lo] <= nums[mid]: if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 # right part is sorted else: if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1 ``` **Why it works**: The `nums[lo] <= nums[mid]` check cleanly separates the two cases, and the standard `lo <= hi` loop with inclusive bounds handles the target finding seamlessly. This is O(log n). > **Note**: There is another two‑step approach: first find the pivot (minimum element) using the **Find Minimum in Rotated Sorted Array** technique, then run ordinary binary search on the appropriate half. That leads us directly to our next problem. * * * ## 3\. Find Minimum in Rotated Sorted Array (LeetCode 153) **Problem**: Find the smallest element in a rotated sorted array with distinct values. Example: `[4,5,6,7,0,1,2]` → `0`. O(log n). ### Binary Search for the Inflection Point We compare `nums[mid]` with `nums[hi]`. * If `nums[mid] > nums[hi]`, the minimum must be **to the right** (the rotation point is in the right half). * If `nums[mid] <= nums[hi]`, the minimum could be at `mid` or **to the left** (the right half is sorted, pivot is in the left half). We can use the **left‑boundary template** to find the index where the condition `nums[i] <= nums[-1]` first becomes true. ```python def findMin(nums): lo, hi = 0, len(nums) - 1 while lo < hi: mid = (lo + hi) // 2 if nums[mid] > nums[hi]: lo = mid + 1 else: hi = mid return nums[lo] ``` **Why** `lo < hi` **and** `mid = (lo+hi)//2`**?** * The condition `nums[mid] > nums[hi]` strictly moves `lo` forward, so we can safely use the lower mid. * When `nums[mid] <= nums[hi]`, we cannot discard `mid` itself (it could be the minimum), so we set `hi = mid`. The loop ends with `lo` pointing at the minimum. **Handling duplicates** (LeetCode 154): If duplicates are allowed, the logic gets trickier. When `nums[mid] == nums[hi]`, we cannot decide whether to go left or right; we safely decrement `hi` by 1. The time complexity becomes O(n) in the worst case. * * * ## 4\. Median of Two Sorted Arrays (LeetCode 4) – O(log(min(m,n))) **Problem**: Given two sorted arrays `nums1` and `nums2` of sizes `m` and `n`, return the median. The overall run time complexity must be O(log(min(m,n))). This is the most challenging problem in our set, but the binary search template makes it manageable. ### Idea: Partition Both Arrays We want to split the combined set into two halves (left and right) of equal size (or left one larger if total is odd) such that every element on the left is ≤ every element on the right. The median will be the maximum of the left half (if odd) or the average of max(left) and min(right). We perform binary search on the **smaller array** (`nums1`) for a partition index `i`. Let `j = (m + n + 1) // 2 - i` be the corresponding partition in `nums2`. We need: ```plaintext maxLeft1 = nums1[i-1] (or -∞ if i==0) minRight1 = nums1[i] (or +∞ if i==m) maxLeft2 = nums2[j-1] (or -∞ if j==0) minRight2 = nums2[j] (or +∞ if j==n) Condition: maxLeft1 <= minRight2 AND maxLeft2 <= minRight1 ``` If condition holds, we’ve found the correct partition. If `maxLeft1 > minRight2` → `i` is too large, so move `hi = i - 1`. If `maxLeft2 > minRight1` → `i` is too small, so move `lo = i + 1`. We use `while lo <= hi` with `mid` being the candidate `i`, but the decision reduces to our classic boundary style. ### Python Code ```python def findMedianSortedArrays(nums1, nums2): # ensure nums1 is the smaller array if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1 m, n = len(nums1), len(nums2) lo, hi = 0, m half_len = (m + n + 1) // 2 while lo <= hi: i = (lo + hi) // 2 j = half_len - i maxLeft1 = float('-inf') if i == 0 else nums1[i-1] minRight1 = float('inf') if i == m else nums1[i] maxLeft2 = float('-inf') if j == 0 else nums2[j-1] minRight2 = float('inf') if j == n else nums2[j] if maxLeft1 <= minRight2 and maxLeft2 <= minRight1: # perfect partition if (m + n) % 2 == 1: return max(maxLeft1, maxLeft2) else: return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2 elif maxLeft1 > minRight2: # i is too far right hi = i - 1 else: # i is too far left lo = i + 1 ``` **Complexity**: O(log(min(m,n))) because we binary search over the smaller array’s length. This is another manifestation of the **left/right boundary pattern**: we adjust `lo` and `hi` based on a condition until we land on the correct `i`. * * * ## 5\. Binary Search on Answer – Koko Eating Bananas & Capacity To Ship Many optimization problems ask: “Find the minimum `X` such that a certain condition holds.” If the condition is **monotonic** (i.e., once it becomes true it stays true for all larger `X`), we can binary search the answer space directly. The answer becomes the **left boundary** of the feasible region. ### Template for “Minimize the Maximum” ```python def binary_search_answer(lo, hi): while lo < hi: mid = (lo + hi) // 2 if feasible(mid): hi = mid else: lo = mid + 1 return lo ``` `feasible(mid)` is a function that returns `True` if `mid` satisfies the required constraint. * * * ### LeetCode 875 – Koko Eating Bananas **Problem**: Koko has `piles[i]` bananas. She has `h` hours. She can choose an eating speed `k` (bananas per hour). Each pile takes `ceil(piles[i] / k)` hours. Find the **minimum** `k` so she finishes within `h` hours. **Feasible condition**: `hours_needed = sum( (pile + k - 1) // k for pile in piles )` ≤ `h` **Search space**: `lo = 1` (slowest possible), `hi = max(piles)` (she can eat any pile in 1 hour, always enough if `h >= len(piles)`). ```python def minEatingSpeed(piles, h): def feasible(k): return sum((pile + k - 1) // k for pile in piles) <= h lo, hi = 1, max(piles) while lo < hi: mid = (lo + hi) // 2 if feasible(mid): hi = mid else: lo = mid + 1 return lo ``` **Dry run**: `piles = [3,6,7,11], h = 8`. * `lo=1, hi=11`. `mid=6` → hours = 1+1+2+2 = 6 ≤ 8, so `hi=6`. * `lo=1, hi=6`, `mid=3` → hours = 1+2+3+4 = 10 > 8, `lo=4`. * `lo=4, hi=6`, `mid=5` → hours = 1+2+2+3 = 8 ≤ 8, `hi=5`. * `lo=4, hi=5`, `mid=4` → hours = 1+2+2+3 = 8 ≤ 8, `hi=4`. Loop ends, return 4. Exactly the left‑boundary template. * * * ### LeetCode 1011 – Capacity To Ship Packages Within D Days **Problem**: Weights `[w1, w2, ...]` must be shipped in order. Find the minimum ship capacity such that we can ship everything within `D` days. Each day we can load up to `capacity` (filling the ship in order without skipping). **Feasible condition**: Greedy simulation – count days needed with given capacity. If `days_needed <= D`, the capacity works. **Search space**: * Lower bound: `max(weights)` (must be able to carry the heaviest package). * Upper bound: `sum(weights)` (one trip if huge capacity). ```python def shipWithinDays(weights, D): def feasible(capacity): days = 1 current_load = 0 for w in weights: if current_load + w > capacity: days += 1 current_load = 0 current_load += w return days <= D lo, hi = max(weights), sum(weights) while lo < hi: mid = (lo + hi) // 2 if feasible(mid): hi = mid else: lo = mid + 1 return lo ``` **Again, the same template**. The magic is in defining `feasible(mid)` and setting the correct `[lo, hi]` bounds. * * * ## 6\. Summary & Practice Guide You’ve now seen that binary search is far more than finding an element in a sorted list. It’s a **pattern language** for shrinking search spaces. ### The Core Templates | Goal | Loop | Mid Calculation | Update Rule | | --- | --- | --- | --- | | First `True` (leftmost) | `while lo < hi` | `mid = (lo + hi) // 2` | True → `hi = mid` | | False → `lo = mid + 1` | | | | | Last `True` (rightmost) | `while lo < hi` | `mid = (lo + hi + 1) // 2` | True → `lo = mid` | | False → `hi = mid - 1` | | | | | Exact match (inclusive) | `while lo <= hi` | `mid = (lo + hi) // 2` | Three‑way comparison with `mid ± 1` | * **Rotated array problems** rely on the sorted half property; `Find Minimum` is a direct left‑boundary search on the condition `nums[mid] > nums[hi]`. * **Median of two sorted arrays** uses binary search on the smaller array’s partition with boundary‑like condition checks. * **Binary search on answer** converts optimization (“minimize max”) into a left‑boundary search over a feasible range. ### Avoid Common Pitfalls * Using `mid = (lo + hi) // 2` when `lo = mid` leads to infinite loops → always pair upper mid with `lo = mid`. * When `hi = mid`, never use upper mid (infinite loop on two elements). * For answer search, ensure the feasibility function is monotonic and the bounds are correct. ### Additional Problems to Cement Your Skills * **LeetCode 278** – First Bad Version (left boundary) * **LeetCode 69** – Sqrt(x) (binary search on answer) * **LeetCode 410** – Split Array Largest Sum (minimize max sum – binary search on answer) * **LeetCode 81** – Search in Rotated Sorted Array II (with duplicates) All binary search problems on leetcode - https://leetcode.com/problem-list/binary-search/ Spend the next two hours coding these templates from scratch. Once the `lo`, `hi`, `mid` dance becomes second nature, you’ll conquer any binary search problem that comes your way. Happy coding!