Binary Search Patterns: The 3 Templates That Solve Every Variation

The mental model that changes everything

Most people think about binary search as "find the middle and check if it matches." That framing works for the simplest case but breaks down immediately when you need to find the first occurrence of a value, or the smallest index satisfying a condition, or the boundary between two regions.

The correct mental model is different: binary search is about eliminating half the search space at every step. You are not looking for a value — you are shrinking the set of positions where the answer could possibly exist. The loop terminates when that set contains exactly one candidate, or zero.

This is why `left = mid + 1` and `right = mid - 1` in the classic template. When you determine that `mid` is not the answer, you exclude it completely. But in boundary-finding templates, `mid` might still be a valid candidate — so you move `right = mid` instead of `mid - 1`, keeping `mid` inside the search space until it can be confirmed or eliminated by further narrowing.

That single distinction — whether to write `mid` or `mid ± 1` when updating a pointer — is responsible for the vast majority of binary search bugs in production code.

Template 1: Exact Match

Use this when the problem asks you to find a specific target value and return its index, or confirm whether it exists. The defining characteristic: if `arr[mid]` equals the target, you're done. There is no ambiguity about whether `mid` could be a better answer elsewhere.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;     // inclusive on both ends

  while (left <= right) {          // <= because a single element is valid
    const mid = left + Math.floor((right - left) / 2);  // avoids overflow

    if (arr[mid] === target) return mid;   // found — exit immediately
    if (arr[mid] < target)  left = mid + 1;  // mid is too small, exclude it
    else                    right = mid - 1; // mid is too large, exclude it
  }

  return -1;  // target not present
}

Template 2: Left Boundary

Use this when the problem asks for the first position satisfying a condition — the leftmost occurrence of a value in an array with duplicates, the smallest valid index, the first true in a predicate function. The key insight is that finding a valid candidate does not end the search, because there might be an equally valid candidate further to the left.

The template achieves this by setting `right = mid` instead of `right = mid - 1` when a candidate is found. This keeps `mid` inside the search space and pushes the right boundary toward it, shrinking the window while preserving the current best answer as a candidate.

function leftBound(arr, target) {
  let left = 0;
  let right = arr.length;           // exclusive upper bound — outside the array

  while (left < right) {            // < not <=, because right is out-of-bounds
    const mid = left + Math.floor((right - left) / 2);

    if (arr[mid] < target) left = mid + 1;  // mid is too small, move past it
    else                   right = mid;      // mid is a candidate — keep it
  }

  // left === right — single candidate remains
  return left < arr.length && arr[left] === target ? left : -1;
}

Template 3: Right Boundary

Use this when the problem asks for the last position satisfying a condition — the rightmost occurrence, the largest valid index, the last true in a predicate. This template is the mirror of Template 2, with one asymmetry that most people get wrong: to avoid an infinite loop, the midpoint must round up instead of down when `left` and `right` are adjacent.

function rightBound(arr, target) {
  let left = 0;
  let right = arr.length - 1;     // inclusive upper bound

  while (left < right) {
    // Round UP to avoid infinite loop when right = left + 1
    const mid = left + Math.ceil((right - left) / 2);

    if (arr[mid] > target) right = mid - 1;  // mid too large, exclude it
    else                   left = mid;        // mid is a candidate — keep it
  }

  return arr[left] === target ? left : -1;
}

The decision framework

Before writing any code, two questions narrow the choice to one template with near-certainty. First: does the problem require finding an exact value, or a boundary position? Second: if it's a boundary, is it the leftmost or rightmost position that satisfies the condition?

The table above is the decision you should make before touching the keyboard. Spend thirty seconds on it. The template follows mechanically once the problem type is clear. Engineers who skip this step and "feel out" the template as they write are the ones who end up with subtle off-by-one bugs that pass the happy path and fail edge cases.

Off-by-one errors: where they actually come from

Off-by-one errors in binary search are not random. They come from exactly two sources: using the wrong template for the problem, and mismatching the loop condition with the pointer update.

The systematic fix is not to memorize which combinations are valid. It's to understand the invariant each template maintains and verify that every pointer update preserves it. For Template 1: after each step, the answer, if it exists, is strictly inside the new `[left, right]`. For Template 2: `right` is always a valid candidate or one position past the end. For Template 3: `left` is always a valid candidate or the leftmost position.

Testing with arrays of size 1 and 2 before submitting will catch the majority of edge case failures. A size-1 array tests whether your loop handles the base case without entering an infinite cycle. A size-2 array tests the adjacent-pointers case that trips up the rounding asymmetry in Template 3.

What interviewers actually look for

In a binary search interview, writing the algorithm correctly is expected. What separates strong candidates is the reasoning they articulate before and during the implementation.

Strong candidates state the invariant before writing the loop. Something like: "I'm using the left boundary template because I need the first index satisfying the condition, not just any index. My right pointer will always point to a valid candidate or one past the end." That sentence shows the interviewer you are reasoning about correctness, not pattern-matching syntax.

They also handle the edge cases explicitly: empty input, target smaller than all elements, target larger than all elements, all elements equal to target. These are one-liner checks once the main logic is correct — but candidates who don't understand the template deeply almost always forget them.

For "binary search on the answer" problems (Koko, Ship Packages, Minimum Days to Make Bouquets), the strongest signal you can give is stating the search space explicitly before binary searching it. "The answer must be between 1 and max(arr) — I'll binary search on that range and check whether each candidate satisfies the constraint." This reframe of the problem from "find a value in an array" to "find the minimum value satisfying a function" is exactly what the problem is testing.

Frequently asked questions