Stop 21 · Data Structures & AlgorithmsTopics · 10/17

Binary Search

In short

Binary search looks easy and still trips up seniors. The idea takes a minute; getting the boundaries right every time takes practice. It's also how database indexes find rows fast.

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 purple blob opens a huge dictionary right in the middle.

Think of it like this

Finding a word in a dictionary

Looking for "mango", you don't start at page 1. You open the middle, see "lemon", and know mango is in the right half. Open the middle of that half, and repeat. A few flips and you're there.

Watch it happen

Finding 23 in 10 sorted numbers

mid

1/3lo = 0, hi = 9. mid = 4, which holds 16. 23 is bigger, so drop the left half.

The big ideas

What you need to know

Halve every step

Each comparison throws away half the remaining items, so 10 lakh sorted items need only about 20 checks.

Data must be sorted

Or at least "monotonic": once the condition becomes true, it stays true. That's what lets you discard a half safely.

Boundaries are the hard part

Pick one style, like lo <= hi with hi = mid - 1, and use it every single time.

Search on the answer

"Smallest capacity that works" type questions binary search over possible answers, not over an array.

See it in code

Walk through the code

1function binarySearch(nums: number[], target: number): number {2  let lo = 0;3  let hi = nums.length - 1;4 5  while (lo <= hi) {6    const mid = lo + Math.floor((hi - lo) / 2);7    if (nums[mid] === target) return mid;8    if (nums[mid] < target) lo = mid + 1; // target is in the right half9    else hi = mid - 1;                    // target is in the left half10  }11  return -1; // not found12}13 14console.log(binarySearch([2, 5, 8, 12, 16, 23, 38, 56, 72, 91], 23)); // 5

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

lo + (hi - lo) / 2 avoids integer overflow in languages like Java and C++. It's a good habit even in JavaScript.

Save yourself the pain

Common mistakes

Oops

Writing lo = mid instead of lo = mid + 1 with a lo <= hi loop.

Do this instead

When lo and hi are next to each other, mid never moves and you loop forever. Always step past mid.

Oops

Running binary search on unsorted data.

Do this instead

Sort first (O(n log n)) if you'll search many times, or use a HashMap for exact lookups.

Your mission

Get the boundaries right

~40 min

Quick check

Roughly how many checks does binary search need for 10 lakh sorted items?

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.