Hack University
← All cheatsheets
Data Structures & Algorithms
Binary Search

Data Structures & Algorithms Cheatsheet

Binary Search

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

When To Reach For This

Binary search needs one thing only: a monotone predicate. Somewhere in the search space, the answer flips from false to true exactly once and never flips back. Sortedness is just the most common way to get that.

Signals in a problem statement:

  • The input is sorted, or rotated-sorted, or the rows and columns of a matrix are sorted.
  • "Find the minimum k such that..." or "the maximum capacity such that...". That is search on the answer.
  • The constraint is huge (n up to 10⁹ or 10¹⁸) but checking one candidate is cheap. Target complexity O(n log n) or O(log n) with an O(n) check.
  • The words first, last, insertion position, floor, or ceiling.
  • "Minimize the maximum" or "maximize the minimum", which is the signature phrasing of the answer-space variant.

Classic problems it solves:

  1. Binary Search and Search Insert Position
  2. Find First and Last Position of Element in Sorted Array
  3. Search in Rotated Sorted Array and Find Minimum in Rotated Sorted Array
  4. Koko Eating Bananas (search on the answer)
  5. Split Array Largest Sum and Capacity To Ship Packages Within D Days
  6. Median of Two Sorted Arrays
  7. Find Peak Element
  8. Kth Smallest Element in a Sorted Matrix

Complexity

VariantTimeSpace
classic search on a sorted arrayO(log n)O(1)
lower_bound or upper_boundO(log n)O(1)
first and last occurrenceO(log n)O(1)
rotated sorted array, distinctO(log n)O(1)
rotated sorted array, duplicatesO(n) worstO(1)
search on the answer, check is O(n)O(n log R)O(1)
sorted matrix, m × n staircase walkO(m + n)O(1)
binary search on prefix sumsO(log n) per queryO(n)

R is the size of the numeric answer range, so log R is around 30–60 for typical bounds.

Exact Match Template

def binary_search(a, target):
    """Return an index of target, or -1. Inclusive bounds."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:                    # <= because hi is a real index
        mid = lo + (hi - lo) // 2      # overflow-safe in Java and C++
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

The three moving parts that must agree: hi is inclusive, the loop is <=, and both branches move past mid. Change one and you get an infinite loop.

Boundary Templates (lower_bound And upper_bound)

These are the two templates worth memorizing. Everything else is a wrapper around them. Both use half-open bounds and lo < hi, and neither ever compares for equality.

def lower_bound(a, target):
    """First index i with a[i] >= target. Returns len(a) if none."""
    lo, hi = 0, len(a)                 # hi is exclusive
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1               # mid is too small, discard it
        else:
            hi = mid                   # mid might be the answer, keep it
    return lo

def upper_bound(a, target):
    """First index i with a[i] > target. Returns len(a) if none."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

The only difference is < versus <=. Derived queries:

QueryExpression
first index of targetlower_bound(a, t), valid if < len(a) and a[i] == t
last index of targetupper_bound(a, t) - 1
count of targetupper_bound(a, t) - lower_bound(a, t)
insertion position (leftmost)lower_bound(a, t)
floor, largest value ≤ targeta[upper_bound(a, t) - 1]
ceiling, smallest value ≥ targeta[lower_bound(a, t)]
strictly less than target, countlower_bound(a, t)

Standard library equivalents, which you should use when allowed:

import bisect
bisect.bisect_left(a, t)          # lower_bound
bisect.bisect_right(a, t)         # upper_bound
bisect.insort(a, t)               # insert keeping sorted, O(n) for the shift
bisect.bisect_left(a, t, lo, hi)  # restricted range
int i = Arrays.binarySearch(a, t);       // any match, or -(insertion) - 1
int ins = i < 0 ? -i - 1 : i;            // recover the insertion point
// Collections.binarySearch works the same on a sorted List
// TreeMap: floorKey, ceilingKey, lowerKey, higherKey
auto it = lower_bound(a.begin(), a.end(), t);   // first >= t
auto jt = upper_bound(a.begin(), a.end(), t);   // first > t
int count = jt - it;
bool found = binary_search(a.begin(), a.end(), t);

Search On The Answer

When the answer is a number and you can verify a candidate faster than you can construct the answer, binary search the answer range. Write the check as a boolean feasible(x) that is monotone, then find the boundary.

def koko_eating_bananas(piles, h):
    """Minimum eating speed to finish in h hours. Feasible is monotone
    increasing in speed, so find the FIRST feasible."""
    def hours(speed):
        return sum((p + speed - 1) // speed for p in piles)   # ceil divide

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid                  # feasible, try slower
        else:
            lo = mid + 1              # too slow
    return lo

def split_array_largest_sum(nums, k):
    """Minimize the largest subarray sum across k splits."""
    def parts_needed(cap):
        parts, cur = 1, 0
        for x in nums:
            if cur + x > cap:
                parts += 1
                cur = x
            else:
                cur += x
        return parts

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if parts_needed(mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

The recipe, every time:

  1. Identify the answer variable and its inclusive range [lo, hi].
  2. Write feasible(x), and confirm it is monotone. If feasible(x) is true then feasible(x + 1) must also be true (or the reverse, consistently).
  3. Use the lo < hi with hi = mid template to find the first true, or lo = mid with a ceiling mid to find the last true.
  4. Set lo and hi to genuinely valid extremes. lo = max(nums) above matters, a smaller lo makes the answer infeasible for every candidate below it.

Floating point version runs a fixed iteration count rather than comparing bounds:

def search_float(feasible, lo=0.0, hi=1e9, rounds=100):
    """100 halvings is well past float64 precision, so no epsilon needed."""
    for _ in range(rounds):
        mid = (lo + hi) / 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid
    return lo

Rotated And Unsorted Variants

def search_rotated(a, target):
    """Distinct values. Decide which half is sorted, then whether the
    target lies inside it. O(log n)."""
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[lo] <= a[mid]:                     # left half is sorted
            if a[lo] <= target < a[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                    # right half is sorted
            if a[mid] < target <= a[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

def find_min_rotated(a):
    """Smallest element, distinct values. Compare mid to the RIGHT end."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[hi]:
            lo = mid + 1                # minimum is strictly right of mid
        else:
            hi = mid                    # mid could be the minimum
    return a[lo]

def find_peak(a):
    """Any local peak in an array with no equal neighbors. O(log n),
    works without sorting because the slope is the predicate."""
    lo, hi = 0, len(a) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < a[mid + 1]:
            lo = mid + 1                # uphill, a peak lies right
        else:
            hi = mid
    return lo

def search_matrix(m, target):
    """Rows and columns sorted ascending. Staircase from the top-right,
    O(rows + cols)."""
    r, c = 0, len(m[0]) - 1
    while r < len(m) and c >= 0:
        if m[r][c] == target:
            return True
        if m[r][c] > target:
            c -= 1
        else:
            r += 1
    return False

Compare mid against hi, not against lo, when hunting the rotation minimum. Comparing to lo fails on an array that was never rotated.

Gotchas

  • Infinite loops. With lo < hi and hi = mid, the mid must round down. If you ever write lo = mid you must round the mid up with (lo + hi + 1) // 2, or lo never advances.
  • Overflow. (lo + hi) / 2 overflows a Java or C++ int near 2³¹. Use lo + (hi - lo) / 2. Python is immune.
  • Inclusive versus exclusive hi. Pick one convention per function and never mix. hi = len(a) - 1 pairs with lo <= hi, hi = len(a) pairs with lo < hi.
  • Duplicates in a rotated array break the O(log n) guarantee. When a[lo] == a[mid] == a[hi] you can only shrink by one, giving O(n) worst case.
  • The predicate must be monotone. Binary searching a non-monotone check returns an arbitrary index, silently.
  • Arrays.binarySearch returns any match, not the first. For first and last occurrence write the boundary template yourself.
  • bisect.insort is O(n), because the list shift dominates the O(log n) search. For many inserts use a heap or a balanced structure.
  • Verify the returned boundary. lower_bound returns len(a) when nothing qualifies, so check the index before dereferencing it.