ENDEAR
Start free
algorithmpro

Binary search

Find a value in a sorted array by halving the search range at every step.

time
O(log n)
space
O(1)

// step through it

step 1 / 9
1function binarySearch(nums, target) {2  let lo = 0, hi = nums.length - 1;3  while (lo <= hi) {4    const mid = Math.floor((lo + hi) / 2);5    if (nums[mid] === target) return mid;6    if (nums[mid] < target) lo = mid + 1;7    else hi = mid - 1;8  }9  return -1;10}
target
= 7
  1. 1lo
  2. 3
  3. 5
  4. 7
  5. 9
  6. 11
  7. 13
  8. 15
  9. 17hi

The array is sorted. Search the whole range: lo = 0, hi = 8.

// pro lesson

Unlock the full walkthrough

This lesson is part of Pro. Pro unlocks every step of every lesson, plus pattern drills and mastery insights.

See pricing

How it works

Look at the middle of the range. If it is the target, you are done. If it is too small, the target can only be in the right half; if it is too big, only in the left half. Halving the range every time means about log₂ n checks, even for millions of items.