Binary Search Patterns: Templates, Rotated Arrays, and Answer Space

---

Why Binary Search Patterns Matter

Binary search looks simple, but it is one of the most error-prone algorithms to implement correctly. Off-by-one errors, infinite loops, and wrong boundary conditions plague even experienced programmers.

The solution is to learn templates — proven patterns that you can apply without reinventing the logic each time.

---

Template 1: Exact Match

The classic binary search: find a specific target in a sorted array.

def binary_search_exact(arr, target):
    """
    Find the index of target in sorted arr.
    Returns -1 if not found.
    """
    lo, hi = 0, len(arr) - 1
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # Avoid overflow
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    
    return -1


arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search_exact(arr, 7))    # 3
print(binary_search_exact(arr, 8))    # -1
print(binary_search_exact(arr, 1))    # 0
print(binary_search_exact(arr, 13))   # 6

Key Points

• Loop condition: lo {'<'}= hi (both inclusive)
• Termination: lo {'>'} hi
• No infinite loop risk: lo or hi always moves by at least 1
• Use case: Finding an exact value in a sorted array

---

Template 2: First True / Lower Bound

Given a monotonic boolean function f(x) that goes from False to True:

F F F F T T T T
          ^ find this

This is the most versatile template. It answers questions like:

• First element >= target (lower_bound)
• First position where a condition becomes true
• Insertion point in a sorted array

def first_true(lo, hi, condition):
    """
    Find the smallest x in [lo, hi] where condition(x) is True.
    Assumes condition goes F...F T...T (monotonic).
    Returns hi + 1 if condition is never True.
    """
    result = hi + 1  # Default: not found
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if condition(mid):
            result = mid    # mid could be the answer
            hi = mid - 1    # but check if there's an earlier True
        else:
            lo = mid + 1    # mid is False, answer must be to the right
    
    return result

Lower Bound (First element >= target)

def lower_bound(arr, target):
    """Find the first index where arr[i] >= target."""
    return first_true(0, len(arr) - 1, lambda mid: arr[mid] >= target)


arr = [1, 3, 3, 5, 7, 7, 7, 9, 11]
print(lower_bound(arr, 3))   # 1 (first 3)
print(lower_bound(arr, 7))   # 4 (first 7)
print(lower_bound(arr, 6))   # 4 (first element >= 6)
print(lower_bound(arr, 12))  # 9 (not found, returns len)

Upper Bound (First element > target)

def upper_bound(arr, target):
    """Find the first index where arr[i] > target."""
    return first_true(0, len(arr) - 1, lambda mid: arr[mid] > target)


arr = [1, 3, 3, 5, 7, 7, 7, 9, 11]
print(upper_bound(arr, 3))   # 3 (first element > 3)
print(upper_bound(arr, 7))   # 7 (first element > 7)

Count Occurrences of a Value

def count_occurrences(arr, target):
    """Count how many times target appears in sorted arr."""
    left = lower_bound(arr, target)
    right = upper_bound(arr, target)
    return right - left


arr = [1, 3, 3, 5, 7, 7, 7, 9, 11]
print(count_occurrences(arr, 7))   # 3
print(count_occurrences(arr, 3))   # 2
print(count_occurrences(arr, 6))   # 0

---

Template 3: Last True / Upper Bound

The mirror of Template 2. Given a function that goes True then False:

T T T T F F F F
      ^ find this

def last_true(lo, hi, condition):
    """
    Find the largest x in [lo, hi] where condition(x) is True.
    Assumes condition goes T...T F...F (monotonic).
    Returns lo - 1 if condition is never True.
    """
    result = lo - 1  # Default: not found
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if condition(mid):
            result = mid    # mid could be the answer
            lo = mid + 1    # check if there's a later True
        else:
            hi = mid - 1    # mid is False, answer must be to the left
    
    return result

Example: Floor (Largest element <= target)

def floor(arr, target):
    """Find the largest element <= target."""
    idx = last_true(0, len(arr) - 1, lambda mid: arr[mid] <= target)
    return arr[idx] if 0 <= idx < len(arr) else None


arr = [1, 3, 5, 7, 9, 11]
print(floor(arr, 6))    # 5
print(floor(arr, 7))    # 7
print(floor(arr, 0))    # None
print(floor(arr, 12))   # 11

---

Search in Rotated Sorted Array

A sorted array rotated at some pivot. At least one half is always sorted.

def search_rotated(nums, target):
    """
    Search in rotated sorted array. LeetCode 33.
    Time: O(log n).
    """
    lo, hi = 0, len(nums) - 1
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if nums[mid] == target:
            return mid
        
        # Determine which half is sorted
        if nums[lo] <= nums[mid]:
            # Left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1  # Target is in sorted left half
            else:
                lo = mid + 1  # Target is in right half
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1  # Target is in sorted right half
            else:
                hi = mid - 1  # Target is in left half
    
    return -1


nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0))    # 4
print(search_rotated(nums, 3))    # -1
print(search_rotated(nums, 6))    # 2

With Duplicates (LeetCode 81)

def search_rotated_duplicates(nums, target):
    """Search in rotated array that may contain duplicates."""
    lo, hi = 0, len(nums) - 1
    
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if nums[mid] == target:
            return True
        
        # Handle duplicates: if we can't determine which half is sorted
        if nums[lo] == nums[mid] == nums[hi]:
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    
    return False

Find Minimum in Rotated Array

def find_min_rotated(nums):
    """Find minimum in rotated sorted array. LeetCode 153."""
    lo, hi = 0, len(nums) - 1
    
    while lo < hi:
        mid = lo + (hi - lo) // 2
        
        if nums[mid] > nums[hi]:
            lo = mid + 1  # Min is in right half
        else:
            hi = mid       # Mid could be min
    
    return nums[lo]


print(find_min_rotated([4, 5, 6, 7, 0, 1, 2]))  # 0
print(find_min_rotated([3, 1, 2]))                 # 1
print(find_min_rotated([1, 2, 3]))                 # 1

---

Peak Element

A peak element is strictly greater than its neighbors.

def find_peak_element(nums):
    """
    Find a peak element. LeetCode 162.
    nums[-1] and nums[n] are -infinity.
    Time: O(log n).
    """
    lo, hi = 0, len(nums) - 1
    
    while lo < hi:
        mid = lo + (hi - lo) // 2
        
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # Peak is to the right
        else:
            hi = mid       # Peak is at mid or to the left
    
    return lo


print(find_peak_element([1, 2, 3, 1]))      # 2
print(find_peak_element([1, 2, 1, 3, 5, 6, 4]))  # 5 (or 1)

---

Binary Search on Answer Space

Instead of searching in an array, search for the answer itself. The idea:

1. Define a range [lo, hi] of possible answers.
2. For each candidate answer mid, check if it is feasible.
3. If feasible, try a better answer (smaller or larger).

Minimize Maximum: Split Array into K Subarrays

def split_array(nums, k):
    """
    Split nums into k subarrays to minimize the maximum subarray sum.
    LeetCode 410.
    """
    def can_split(max_sum):
        """Can we split into <= k subarrays with each sum <= max_sum?"""
        count = 1
        current_sum = 0
        
        for num in nums:
            if current_sum + num > max_sum:
                count += 1
                current_sum = num
                if count > k:
                    return False
            else:
                current_sum += num
        
        return True
    
    lo = max(nums)       # At minimum, max_sum >= largest element
    hi = sum(nums)       # At maximum, one subarray holds everything
    
    result = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if can_split(mid):
            result = mid
            hi = mid - 1   # Try smaller maximum
        else:
            lo = mid + 1   # Need larger maximum
    
    return result


nums = [7, 2, 5, 10, 8]
print(split_array(nums, 2))  # 18 (split: [7,2,5] and [10,8])

Koko Eating Bananas

import math

def min_eating_speed(piles, h):
    """
    Minimum eating speed to finish all bananas in h hours. LeetCode 875.
    """
    def can_finish(speed):
        hours = sum(math.ceil(pile / speed) for pile in piles)
        return hours <= h
    
    lo, hi = 1, max(piles)
    
    result = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        
        if can_finish(mid):
            result = mid
            hi = mid - 1
        else:
            lo = mid + 1
    
    return result


piles = [3, 6, 7, 11]
print(min_eating_speed(piles, 8))   # 4
print(min_eating_speed(piles, 30))  # 1

Capacity to Ship Packages

def ship_within_days(weights, days):
    """
    Minimum ship capacity to deliver all packages in 'days' days. LeetCode 1011.
    """
    def can_ship(capacity):
        day_count = 1
        current_load = 0
        
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = w
            else:
                current_load += w
        
        return day_count <= days
    
    lo = max(weights)
    hi = sum(weights)
    
    result = hi
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            result = mid
            hi = mid - 1
        else:
            lo = mid + 1
    
    return result


weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(ship_within_days(weights, 5))  # 15

---

Common Mistakes and How to Avoid Them

Mistake 1: Overflow in Mid Calculation

# Wrong (can overflow in languages like C++/Java):
mid = (lo + hi) // 2

# Correct:
mid = lo + (hi - lo) // 2

Python handles big integers natively, but use the safe form for portability.

Mistake 2: Infinite Loop

# WRONG: infinite loop when lo == hi and condition sends to lo = mid
while lo < hi:
    mid = (lo + hi) // 2
    if condition(mid):
        hi = mid
    else:
        lo = mid  # BUG: when lo + 1 == hi, mid == lo, loop never ends

# FIX: use lo = mid + 1, or use mid = (lo + hi + 1) // 2 for the else branch

Mistake 3: Wrong Loop Condition

Template	Loop condition	What lo/hi represent
Exact match	lo {'<'}= hi	Both inclusive
First/Last true	lo {'<'}= hi	Search space
Peak/Min	lo {'<'} hi	Converge to one element

Mistake 4: Forgetting Edge Cases

Always test:

• Empty array
• Single element
• Target smaller than all elements
• Target larger than all elements
• All elements are the same

def test_binary_search():
    assert binary_search_exact([], 5) == -1
    assert binary_search_exact([5], 5) == 0
    assert binary_search_exact([5], 3) == -1
    assert lower_bound([1, 1, 1], 1) == 0
    assert lower_bound([1, 1, 1], 2) == 3
    print("All tests passed!")

test_binary_search()

---

Python’s bisect Module

Python provides bisect for binary search:

import bisect

arr = [1, 3, 3, 5, 7, 7, 7, 9, 11]

# bisect_left = lower_bound (first >= target)
print(bisect.bisect_left(arr, 7))    # 4

# bisect_right = upper_bound (first > target)
print(bisect.bisect_right(arr, 7))   # 7

# Insert while maintaining sorted order
bisect.insort(arr, 6)
print(arr)  # [1, 3, 3, 5, 6, 7, 7, 7, 9, 11]

# Check if value exists
def binary_search(arr, target):
    idx = bisect.bisect_left(arr, target)
    return idx < len(arr) and arr[idx] == target

print(binary_search(arr, 7))   # True
print(binary_search(arr, 8))   # False

---

Practice Problems

1. Binary Search (LeetCode 704) — Template 1.
2. First Bad Version (LeetCode 278) — Template 2 (first True).
3. Search Insert Position (LeetCode 35) — Lower bound.
4. Search in Rotated Sorted Array (LeetCode 33) — Rotated pattern.
5. Find Peak Element (LeetCode 162) — Peak pattern.
6. Split Array Largest Sum (LeetCode 410) — Answer space.
7. Koko Eating Bananas (LeetCode 875) — Answer space.
8. Capacity to Ship Packages (LeetCode 1011) — Answer space.
9. Find Minimum in Rotated Array (LeetCode 153) — Rotated pattern.
10. Median of Two Sorted Arrays (LeetCode 4) — Advanced binary search.

---

Key Takeaways

• Learn three templates: exact match, first true (FFFTTT), and last true (TTTFFF). These cover almost every binary search variant.
• In rotated arrays, one half is always sorted. Check which half, then decide where the target could be.
• Binary search on answer space transforms optimization problems into decision problems: “Can I achieve answer = mid?”
• Always use mid = lo + (hi - lo) // 2 to avoid overflow.
• Test edge cases: empty array, single element, target outside range, all duplicates.
• Python’s bisect module provides battle-tested implementations for lower/upper bound.