Fresher · Binary search

Binary Search · Find a Sorted Value

Given strictly increasing integers, return the index of target or -1. Do not mutate the array. Explain why each comparison can discard half of the remaining interval.

Examples

[1, 3, 7, 9], 7 → 2

Compare approaches

Linear scan

Inspect values until a match is found; sorting is not used.

Time: O(n) · Space: O(1)

function search(nums, target) { return nums.indexOf(target); }

Halve a closed interval

If present, the target stays inside [lo, hi]. Each iteration removes the midpoint and one half.

Time: O(log n) · Space: O(1)

function search(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;
}

Common traps

This contract requires sorted input.
Using lo = mid can repeat the same interval forever.

Practise in the workspace →