Binary search: patterns, templates and common pitfalls

Binary search finds a target in a sorted sequence by repeatedly halving the search range. Each step discards half, so it runs in O(log n). For a million items that is about 20 steps instead of up to a million.

The idea is simple. Getting the details right (boundaries, off-by-one, infinite loops) is the hard part, so learn a template and stick to it.

The classic version

Find the index of target in a sorted array, or -1.

function binarySearch(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
// Time O(log n), space O(1)

Key points:

• The range [lo, hi] is inclusive and the loop runs while it is not empty (lo <= hi).
• mid = lo + (hi - lo) / 2 avoids integer overflow in languages with fixed-size integers (like Java, C++, Go). (lo + hi) / 2 can overflow.
• When you move a bound, you skip mid (mid + 1 or mid - 1) since you already checked it.

The more useful form: find the first position where a condition becomes true

Most variations are really this: there is a boundary where a yes/no condition flips from false to true, and you want the first true. This template handles lower bound, upper bound, first and last occurrence and "search on answer".

// returns the first index in [0, n) where isTrue(index) is true, or n if none
function firstTrue(n, isTrue) {
  let lo = 0, hi = n;                 // half-open [lo, hi)
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (isTrue(mid)) hi = mid;        // mid could be the answer, keep it
    else lo = mid + 1;                // mid is false, discard it
  }
  return lo;
}

The range is half-open [lo, hi), and hi = mid keeps a possible answer. This version always shrinks, so it cannot loop forever.

Lower bound and upper bound

• Lower bound (first index with nums[i] >= target): isTrue = i => nums[i] >= target.
• Upper bound (first index with nums[i] > target): isTrue = i => nums[i] > target.
• First occurrence of target: lower bound, then check that the value matches.
• Last occurrence: upper bound minus 1, then check.
• Count of target: upper bound minus lower bound.
• Insert position: the lower bound.

Searching on the answer

Binary search works on any monotonic yes/no question, not only on arrays. If you can ask "is value x enough?" and the answer flips once as x grows, you can search x directly.

Problem: the minimum eating speed so that all piles are finished within h hours (Koko Eating Bananas).

function minSpeed(piles, h) {
  const canFinish = (speed) =>
    piles.reduce((hours, p) => hours + Math.ceil(p / speed), 0) <= h;
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canFinish(mid)) hi = mid; else lo = mid + 1;
  }
  return lo;
}
// Time O(n log M), where M is the largest pile

Typical "search on answer" problems: minimise the maximum (split array, ship packages within D days), maximise the minimum (aggressive cows), square root, capacity and rate problems. The clue: "find the smallest/largest value such that something is possible".

Rotated sorted array

Array like [4,5,6,7,0,1,2] was sorted then rotated. At any mid, one half is always sorted. Decide which half is sorted, check whether the target lies inside it, and discard the other half.

function searchRotated(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {                 // left half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                     // right half is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

(With duplicates the problem gets harder and can degrade to O(n).)

Common pitfalls

• Infinite loops: moving lo = mid or hi = mid with the wrong mid rounding. Stick to one template.
• Off-by-one: mixing inclusive hi = n - 1 with half-open hi = n. Pick one style.
• Overflow in (lo + hi) / 2 in fixed-size integer languages.
• Unsorted input: binary search needs sorted data (or a monotonic condition).
• Forgetting the empty array and single-element cases.
• Wrong boundaries for "search on answer": make sure the true answer lies within [lo, hi].

Practice problems

Binary Search, Search Insert Position, First and Last Position of Element, Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array, Koko Eating Bananas, Capacity to Ship Packages, Median of Two Sorted Arrays (hard).

Takeaway: use binary search whenever data are sorted or a yes/no condition flips once. Learn the "first true" template with a half-open range, and remember it works on answers, not just arrays.

---

Interview prep and DSA series, Part 1 (core patterns): 4 of 5. Previous: Two pointers and sliding window: patterns with examples.