CodeMosa

Master LeetCode Patterns

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)

What is Binary Search?

#
Definition: Halve a sorted/monotonic search space each step to locate targets or boundaries.

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

How Binary Search works

#

Three canonical forms: index search, lower/upper bound, and binary search on answer with a monotone feasibility predicate.

  • Sorted or rotated sorted array
  • First/last occurrence, lower/upper bound
  • Predicate monotonic in threshold

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

Related Collections

#
Curated practice sets for this pattern
Binary Search Practice Problems

Code Templates

#
Three canonical forms: index search, lower/upper bound, and binary search on answer with a monotone feasibility predicate.
# Binary Search Templates
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

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

def binary_search_answer(lo, hi, feasible):
    # feasible(x) returns True/False, monotonic in x
    while lo < hi:
        mid = (lo + hi)//2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Pattern Variants & Approaches

#
Different methodologies and implementations for this pattern
1

Lower vs 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 Array

#

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

Binary 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
4

Lower/Upper Bound Templates

#

Battle-tested templates and off-by-one edge cases for boundaries across languages

When to Use This Variant
  • Insertion index
  • First/last position
  • Duplicates present
Use Case
Return insertion points and ranges reliably across languages
Advantages
  • Battle-tested templates
  • Avoids infinite loops
  • Consistent semantics
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

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

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