LeetCode 704 · Easy · Binary Search

Binary Search

Given an array nums of distinct integers sorted in ascending order and a target, return the index of target, or -1 if it is missing, in O(log n) time.

O(log n)time
O(1)space
÷ 2range per probe

nums: 1–16 distinct integers, sorted ascending, −999 to 999 · target: −9999 to 9999

public int search(int[] nums, int target) { int l = 0; int r = nums.length - 1; while (l <= r) { // [l, r] inclusive int m = l + (r - l) / 2; // no overflow if (nums[m] > target) { r = m - 1; } else if (nums[m] < target) { l = m + 1; } else { return m; } } return -1;}
l
—
r
—
m
—
nums[m]
—
r − l + 1
—

Why it works

  1. A linear scan ignores the sort: O(n). One look at the middle tells you which half cannot hold the target, so every probe halves the range: at most ⌈log₂(n+1)⌉ probes, 5 for 16 values, 30 for a billion.
  2. Invariant: if target is anywhere, it is inside [l, r]. It starts as the whole array, and each move throws away only cells that are proven wrong.
  3. Why l <= r: both ends are inclusive, so l == r is still one unchecked cell. With l < r, [5] with target 5 returns -1. Why m ± 1: nums[m] is already ruled out. Writing r = m keeps it, and once l == r == m the loop never ends.
  4. Why l + (r - l) / 2: it equals (l + r) / 2, but l + r can overflow a 32-bit int and go negative once the array has over a billion cells. l + (r - l) / 2 never leaves the range [l, r].
  5. O(log n) time, O(1) space. On a miss the loop ends with l = r + 1, and l is exactly where target would be inserted: return l instead of -1 and you have 35 Search Insert Position.