Binary Search Patterns: Search Space, Boundaries, and Rotated Arrays

Binary search is not just for finding an element in a sorted array. It is a general technique for reducing a search space by half at each step. Whenever you can define a condition that partitions the search space into two halves (all True on one side, all False on the other), binary search applies. This guide covers every major pattern.

Pattern 1: Standard Binary Search

Find the exact position of a target in a sorted array.

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # avoid overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))   # -1

// Java version
public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Pattern 2: Left Boundary (First Occurrence)

Find the first position where the target appears, or the insertion point if it does not exist.

Array: [1, 2, 2, 2, 3, 4]   target=2

Step 1: left=0, right=6, mid=3 -> nums[3]=2 >= 2 -> right=3
Step 2: left=0, right=3, mid=1 -> nums[1]=2 >= 2 -> right=1
Step 3: left=0, right=1, mid=0 -> nums[0]=1 < 2  -> left=1
left=1, right=1 -> left=right -> answer=1 (first occurrence of 2)

def bisect_left(nums: list[int], target: int) -> int:
    """Find the leftmost position where target can be inserted."""
    left, right = 0, len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left

# First occurrence of 2
arr = [1, 2, 2, 2, 3, 4]
idx = bisect_left(arr, 2)
print(f"First 2 at index: {idx}")  # 1

Pattern 3: Right Boundary (Last Occurrence)

def bisect_right(nums: list[int], target: int) -> int:
    """Find the rightmost position after all occurrences of target."""
    left, right = 0, len(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left

# Last occurrence of 2
arr = [1, 2, 2, 2, 3, 4]
idx = bisect_right(arr, 2) - 1
print(f"Last 2 at index: {idx}")  # 3

Problem: Find First and Last Position (LC 34)

def searchRange(nums: list[int], target: int) -> list[int]:
    def find_left(nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
    
    def find_right(nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left - 1
    
    left_idx = find_left(nums, target)
    right_idx = find_right(nums, target)
    
    if left_idx <= right_idx and left_idx < len(nums) and nums[left_idx] == target:
        return [left_idx, right_idx]
    return [-1, -1]

print(searchRange([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
print(searchRange([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]

Pattern 4: Rotated Sorted Array

A sorted array that has been rotated at some pivot.

Search in Rotated Array (LC 33)

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if nums[mid] == target:
            return mid
        
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

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

// Java version
public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}

Find Minimum in Rotated Array (LC 153)

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1  # min is in right half
        else:
            right = mid     # mid could be the min
    
    return nums[left]

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

Pattern 5: Binary Search on Answer

Instead of searching in an array, binary search on the answer space. This applies when you need to find the minimum or maximum value that satisfies a condition.

Koko Eating Bananas (LC 875)

def minEatingSpeed(piles: list[int], h: int) -> int:
    def can_finish(speed):
        hours = sum((pile + speed - 1) // speed for pile in piles)
        return hours <= h
    
    left, right = 1, max(piles)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid       # try a slower speed
        else:
            left = mid + 1    # need to eat faster
    
    return left

print(minEatingSpeed([3, 6, 7, 11], 8))    # 4
print(minEatingSpeed([30, 11, 23, 4, 20], 5))  # 30

Capacity to Ship Packages (LC 1011)

def shipWithinDays(weights: list[int], days: int) -> int:
    def can_ship(capacity):
        day_count = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days
    
    left = max(weights)       # must fit the heaviest package
    right = sum(weights)       # ship everything in one day
    
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

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

Split Array Largest Sum (LC 410)

def splitArray(nums: list[int], k: int) -> int:
    def can_split(max_sum):
        count = 1
        current = 0
        for num in nums:
            if current + num > max_sum:
                count += 1
                current = 0
            current += num
        return count <= k
    
    left = max(nums)
    right = sum(nums)
    
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid
        else:
            left = mid + 1
    
    return left

print(splitArray([7, 2, 5, 10, 8], 2))  # 18

Common Pitfalls

1. Off-by-One Errors

The two main templates differ in their loop condition and boundary updates:

# Template A: left <= right (inclusive right boundary)
# Use when: searching for exact match
# right starts at len(nums) - 1
# Update: left = mid + 1, right = mid - 1

# Template B: left < right (exclusive right boundary)
# Use when: finding boundaries or search-on-answer
# right starts at len(nums) or upper_bound
# Update: left = mid + 1, right = mid

2. Integer Overflow

Always compute mid as left + (right - left) // 2 instead of (left + right) // 2 to avoid overflow in languages like Java and C++.

3. Infinite Loops

If right = mid - 1 is used with left < right, you can skip valid answers. If right = mid is used with left <= right, you get infinite loops. Match the template consistently.

Pattern Recognition Guide

Key Takeaways

Binary search works whenever you can split a search space into two halves based on a monotonic condition. Use the inclusive template (left <= right) for exact-match problems. Use the exclusive template (left < right) for boundary-finding and search-on-answer problems. For rotated arrays, determine which half is sorted and check if the target falls in that range. For search-on-answer problems, define a can_do(mid) function and binary search on the answer space. Always verify your template handles the edge case where the answer is at the boundary.