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:

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):

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):

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:

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).

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.

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:

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

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”

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)).

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).

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!