Stop 21 · Data Structures & AlgorithmsTopics · 10/17

Binary Search

In short

Binary search sounds like a 5-line idea, yet it's the one people get wrong under pressure, with off-by-one errors and infinite loops. Learn one template and stick to it.

An O(log n) search technique for finding a target in sorted data by repeatedly halving the search space — deceptively easy to get subtly wrong at the boundaries.

The jaadu flips a thick dictionary open right in the middle.

Think of it like this

Finding a word in a dictionary

Looking for 'mango', you don't read from page 1. You open the middle, see 'kite', and know mango is later. Each flip throws away half the book. A thousand pages need only about ten flips.

Watch it happen

Finding 23 in 10 sorted numbers

mid

1/3mid = floor((0 + 9) / 2) = 4, which holds 16. 16 < 23, so the answer is on the right.

The big ideas

What you need to know

Needs sorted (or monotonic) data

You must be able to say 'the answer is on the left' or 'on the right' after each check.

Halves every step

So it's O(log n). A million items need about 20 checks.

One template, always

lo = 0, hi = n - 1, loop while lo <= hi. Move lo to mid + 1 or hi to mid - 1.

Search on the answer

Questions like 'minimum speed to finish in time' can be binary searched over possible answers.

See it in code

Walk through the code

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

1/4The search range starts as the whole array.

The range halves each loop, so time is O(log n). Only lo, hi and mid are stored, so space is O(1).

Save yourself the pain

Common mistakes

Oops

Writing lo = mid instead of lo = mid + 1 and getting an infinite loop.

Do this instead

mid has already been checked, so skip it: mid + 1 or mid - 1.

Oops

Binary searching an unsorted array.

Do this instead

The 'go left or right' decision only makes sense on sorted or monotonic data.

Your mission

Search, then search smarter

~40 min

Quick check

Roughly how many checks does binary search need on a sorted array of 1,000,000 items in the worst case?

Go deeper

1Implement binary search from scratch without looking it up, including edge cases.
2Solve 'search in rotated sorted array' as a classic binary-search variant.
3Recognize binary-search-shaped problems: anything about a sorted (or monotonic) search space.