Interview OS
Back to Coding Prep

Coding

Binary search

Halve the search space on a monotonic predicate.

Coding pattern

Overview

Binary search halves a sorted (or monotonic) search space each step for O(log n) answers. The advanced version — 'binary search on the answer' — applies to any predicate that flips from false to true, well beyond plain array lookups.

How it works

Coding pattern
InputBoundsHalveOutputSorted spacesortedlo / hilo=0,hi=nmid checkO(log n)Target
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Sorted space

    • A monotonic array or answer space.
  2. 2

    lo / hi

    • Set the search range.
  3. 3

    mid check

    • Discard half the range each step.
  4. 4

    Target

    • Return the index or first-true boundary.
    • Example: Search insert, sqrt

When to reach for it

  • Sorted lookups
  • 'Smallest x that works'
  • Search on answer space

Example problem

Find the insert position of a target.

Approach

  • Maintain lo/hi
  • Compare mid, move the boundary that can't contain the answer

Solution

function searchInsert(nums, target) {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    nums[mid] < target ? lo = mid + 1 : hi = mid;
  }
  return lo;
}

Complexity

Time O(log n), Space O(1).

Common pitfalls

  • Infinite loops from bad mid update
  • Inclusive vs exclusive bounds

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions