Frontend Beauty
ESC

Type to search the knowledge base.

Binary Search

Search a sorted array in O(log n) — classic template, boundary bugs, and the first-true / last-true variants.

beginner4 min read
  • dsa
  • binary-search
  • arrays
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft
  • Apple

The problem

Given a sorted array of distinct integers nums and a target, return the index of target, or -1 if missing.

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1

This is the pattern, not just one LC problem. Half of “binary search on answer” interview questions reuse the same loop skeleton.

Brute force

Linear scan O(n). Fine for tiny n; interviewer wants log n when the array is sorted.

function searchLinear(nums: number[], target: number): number {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) return i;
  }
  return -1;
}

Maintain inclusive window [lo, hi]:

  1. While lo ≤ hi
  2. mid = lo + ((hi - lo) >> 1) — avoids overflow habits from other languages; in JS still fine
  3. If nums[mid] === target return mid
  4. If nums[mid] < target → lo = mid + 1
  5. Else → hi = mid - 1
  6. Return -1
function search(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    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)

Why not mid = (lo + hi) / 2?

In JS numbers are floats; for array indices Math.floor((lo + hi) / 2) works for practical sizes. Prefer the shift form or Math.floor explicitly so you never leave a float index.

Template: lower bound (first index ≥ target)

Useful when duplicates exist or you need insert position (LC 35 Search Insert Position).

function lowerBound(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length; // exclusive hi

  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo; // in [0, n]
}

Then classic “found?” is lo < n && nums[lo] === target.

Template: binary search on a predicate

When the array is not “find value” but “find minimal capacity / first bad version / peak”:

  • Define feasible(x) → boolean monotonic: false false … true true
  • Binary search for the first true
function firstTrue(n: number, feasible: (x: number) => boolean): number {
  let lo = 0;
  let hi = n; // or domain max + 1
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (feasible(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Edge cases

  • Empty array → -1
  • One element
  • Target smaller than all / larger than all
  • Even vs odd length (mid bias does not matter if update rules are correct)
  • Duplicates — classic distinct version; otherwise specify first/last occurrence

Common bugs

  • while (lo < hi) with hi = mid - 1 inconsistently → infinite loop or missed ends
  • Using exclusive vs inclusive bounds mixed in one function
  • Off-by-one: hi = nums.length vs nums.length - 1
  • Integer mid as float: always floor

Rule of thumb: pick one template (inclusive or half-open) and stick to it for the whole interview.

Follow-ups

  1. Search in Rotated Sorted Array
  2. Find Minimum in Rotated Sorted Array
  3. First / last position of element
  4. Binary search on answer (Koko eating bananas, capacity to ship packages)

Interview delivery

  1. Confirm sorted + distinct (or not).
  2. State O(log n).
  3. Write one clean template.
  4. Trace target present and absent.
  5. Mention lower-bound if duplicates come up.

Further reading