BeginnerSearching

Binary Search

Divide search space by half to find boundaries, handle rotations, or search on the answer

Time: O(log n) or O(n log R)
Space: O(1)
Pattern Overview

Core Idea

Maintain an invariant over a sorted or monotonic space; shrink [lo, hi] toward the boundary/target with careful mid updates.

When to Use

Use on sorted arrays, unimodal functions, monotonic predicate checks, or optimization by 'binary search on answer'.

General Recognition Cues
General indicators that this pattern might be applicable
  • Sorted or rotated sorted array
  • First/last occurrence, lower/upper bound
  • Predicate monotonic in threshold
  • Minimize max or maximize min
  • Mountain/bitonic array
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Boundary Search (Lower/Upper Bound)

Find first true/last true index by steering toward boundary

When to Use This Variant
  • First/last occurrence
  • >= x or > x boundary
  • Range of target
Use Case
Frequency ranges, duplicates, insertion points
Advantages
  • Deterministic O(log n)
  • Robust invariant
  • Reusable template
Implementation
def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # first index with arr[i] >= target

def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo  # first index with arr[i] > target
2

Rotated Arrays

Leverage one sorted half to guide search

When to Use This Variant
  • Pivoted sorted array
  • One half sorted at mid
  • Choose side by target
Use Case
Search target in rotated array
Advantages
  • O(log n) without finding pivot
  • Simple branching
  • No extra space
Implementation
def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if 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 -1
3

Search on Answer

Binary search feasible answers using a monotonic check

When to Use This Variant
  • Minimize maximum / maximize minimum
  • Feasibility check O(n)
  • Range [lo, hi] from data
Use Case
Capacity, speed, partitioning problems
Advantages
  • Turns optimization into decision
  • Clean O(n log range)
  • Greedy check often suffices
Implementation
def min_speed(piles, h):
    # Koko Eating Bananas style feasibility check
    import math
    lo, hi = 1, max(piles)
    def can(k):
        return sum((p + k - 1) // k for p in piles) <= h
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
Common Pitfalls
Watch out for these common mistakes
  • Off-by-one on boundaries
  • Endless loops with mid/lo/hi updates
  • Overflow when computing mid
  • Wrong predicate direction
  • Not proving monotonicity before searching
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
O(log n) or O(n log R)

Array search is O(log n); answer search is O(log R) checks times O(n) per check.

Space Complexity
O(1)

Iterative search uses constant space.

Ready to test your knowledge?

Test your pattern recognition with interactive questions