The Binary Search Pattern: Template & When to Use It

The binary search pattern repeatedly halves a search space, discarding the half that cannot contain the answer, to find a target in O(log n). It applies far beyond sorted arrays: any time a yes/no test is monotonic over a numeric range — false, false, …, true, true — you can binary-search for the boundary. This page recaps both forms and gives templates.

For the topic pages, see binary search and binary search on the answer.

The signal: when to recognize it

The data is sorted (or can be sorted) and you need to find a value or a boundary — first/last occurrence, insertion point, smallest element ≥ x.
The complexity budget is O(log n) or O(n log n) — a strong hint that a binary search hides inside.
“Minimize the maximum” / “maximize the minimum” / “smallest capacity/speed/value such that something fits.” This is the binary-search-on-answer signal.
You can write a function feasible(x) whose answer is monotonic: once it’s true for some x, it stays true for all larger (or all smaller) x.

For beginners: Think of guessing a number 1–100 where each guess is told “too high” or “too low.” Halving the range every guess finds it in 7 tries instead of 100. Binary search is that game, applied to any sorted or monotonic space.

Template: classic search on a sorted array

The half-open [lo, hi) style avoids most off-by-one bugs. Returns the index of target, or -1.

#include <vector>
// Classic binary search on a sorted array. Returns index or -1.
int binarySearch(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size();      // [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;    // avoids overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return -1;
}

// Classic binary search on a sorted array. Returns index or -1.
int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length;           // [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;    // avoids overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return -1;
}

// Classic binary search on a sorted array. Returns index or -1.
function binarySearch(a, target) {
  let lo = 0, hi = a.length;            // [lo, hi)
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return -1;
}

# Classic binary search on a sorted array. Returns index or -1.
def binary_search(a, target):
    lo, hi = 0, len(a)        # [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return -1

Template: binary search on the answer

When the answer is a number in a range and feasible(x) is monotonic (false → true as x grows), search for the smallest feasible x. The example: smallest divisor so that the sum of ceil(num / divisor) stays within threshold.

#include <vector>
#include <algorithm>
// Smallest divisor d such that sum(ceil(n / d)) <= threshold.
int smallestDivisor(const std::vector<int>& nums, int threshold) {
    auto feasible = [&](int d) {
        long total = 0;
        for (int n : nums) total += (n + d - 1) / d;   // ceil division
        return total <= threshold;
    };
    int lo = 1, hi = *std::max_element(nums.begin(), nums.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;       // mid works; try smaller
        else lo = mid + 1;                 // mid too small a divisor
    }
    return lo;
}

// Smallest divisor d such that sum(ceil(n / d)) <= threshold.
int smallestDivisor(int[] nums, int threshold) {
    int lo = 1, hi = 0;
    for (int n : nums) hi = Math.max(hi, n);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        long total = 0;
        for (int n : nums) total += (n + mid - 1) / mid;  // ceil division
        if (total <= threshold) hi = mid;  // mid works; try smaller
        else lo = mid + 1;                 // mid too small a divisor
    }
    return lo;
}

// Smallest divisor d such that sum(ceil(n / d)) <= threshold.
function smallestDivisor(nums, threshold) {
  const feasible = (d) =>
    nums.reduce((sum, n) => sum + Math.ceil(n / d), 0) <= threshold;
  let lo = 1, hi = Math.max(...nums);
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;           // mid works; try smaller
    else lo = mid + 1;                     // mid too small a divisor
  }
  return lo;
}

import math
# Smallest divisor d such that sum(ceil(n / d)) <= threshold.
def smallest_divisor(nums, threshold):
    def feasible(d):
        return sum(math.ceil(n / d) for n in nums) <= threshold
    lo, hi = 1, max(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid        # mid works; try smaller
        else:
            lo = mid + 1    # mid too small a divisor
    return lo

Complexity

Classic search is O(log n) time, O(1) space. Binary search on the answer is O(log(range) · cost(feasible)) — for the divisor example, O(n · log(maxValue)), since each feasibility check scans all n numbers.

Common pitfalls

Overflow: compute mid = lo + (hi - lo) / 2, not (lo + hi) / 2, in fixed-width languages.
Loop that never terminates: make sure each branch strictly shrinks the range. With [lo, hi), lo = mid + 1 and hi = mid both guarantee progress.
Wrong monotonicity direction: confirm whether feasible goes false → true or true → false, and aim the update accordingly.
Boundaries on “answer” search: lo/hi must bracket a range that contains a feasible value.

Going deeper: First-occurrence and last-occurrence searches are the same skeleton with the comparison changed to keep moving past equal elements — see binary search variations.

Practice

Drill it in the searching exercises. It composes well with greedy and sliding window checks inside feasible.