Binary search

What you'll learn

How binary search works, why it needs sorted data, and why it is O(log n).

Why it matters

Searching a million sorted items takes at most about 20 steps with binary search, versus up to a million with a simple scan. This idea shows up in databases, version control and many interview questions.

Explanation

Linear search checks each item in turn: O(n).

Binary search works on a sorted list. Look at the middle item:

• If it is the target, done.
• If the target is bigger, throw away the left half.
• If the target is smaller, throw away the right half.

Repeat on what is left. Each step halves the search area, so the number of steps is about log2(n): O(log n).

Example

Step-by-step walkthrough

2

5

8

12

16

23

38

56

72

91

The list is sorted. Find 23 by halving the search area each time.

Play

1. low is 0 and high is 9, so mid is 4 and the value there is 16.
2. 16 < 23, so the target must be on the right. low becomes 5.
3. mid is now 7, value 56. 56 > 23, so high becomes 6.
4. mid is 5, value 23. Found at index 5 after three looks.
5. Searching for 7 shrinks the range until low > high, and the function returns -1.

Try it yourself

Count how many loop rounds it takes to find 72. Add a counter and print it.

Binary search with a step counterJavaScript

Editable codefunction binarySearch(sorted, target) { let low = 0; let high = sorted.length - 1; let steps = 0; while (low <= high) { steps++; const mid = Math.floor((low + high) / 2); if (sorted[mid] === target) return { index: mid, steps }; if (sorted[mid] < target) low = mid + 1; else high = mid - 1; } return { index: -1, steps }; } const nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]; console.log(binarySearch(nums, 72));

Run ResetCopyCtrl+Enter to run

Common mistakes

• Running it on unsorted data. Results are wrong.
• Infinite loop from forgetting + 1 / - 1 when moving low or high.
• Using < instead of <= in the loop condition, which misses the last item.
• Overflow of (low + high) in some languages with fixed-size integers.

Quick quiz

Summary

• Binary search needs sorted data.
• Halving the range each step gives O(log n).
• Watch the boundaries: low <= high, and move by mid + 1 / mid - 1.

Next: trees.

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

const nums = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
console.log(binarySearch(nums, 23));  // 5
console.log(binarySearch(nums, 7));   // -1