Binary Search
Find a number in a sorted array by repeatedly checking the middle and throwing away the half that can't contain it.
- Classic binary search
Before this, know: Arrays and indexes, Sorted order
You get an array nums that is sorted in ascending order (smallest to
largest, no repeats) and a number target. Return the index (position,
starting from 0) where target sits, or -1 if it isn’t there.
- -10
- 01
- 32
- 53
- 94
- 125
With the same array and target = 2, the answer is -1: there is no 2.
The one real rule: your solution must run in O(log n) time. Reading the array from left to right is too slow. We’ll see what O(log n) means and why the sorting makes it possible.
A sorted array is the same game. Look at the middle item. If it’s too small, the target can only be to its right, because everything to its left is even smaller. If it’s too big, the target can only be to its left. Either way, half the array is gone after a single look.
Pause and think
12 > 8, and the array is sorted, so 8 and everything to its left (2, 4, 6) are
too small. Throw away indexes 0 to 3. Only [10, 12, 14] (indexes 4 to 6) is
left. Its middle is 12: found it, on the second look.
Check every item from the left until you find the target or run out.
Brute force: check every item
nums = [1, 3, 5, 7, 9, 11, 13], target = 11
- 10
- 31
- 52
- 73
- 94
- 115
- 136
- target
- 11
- looks
- 1
- result
- —
- Checking
- Already checked
- Target
Look #1: nums[0] = 1, not 11. Move on.
Which line is running?
function search(nums, target) { for (let i = 0; i < nums.length; i++) {Running now: if (nums[i] === target) return i; } return -1;}Brute force: linear search
function search(nums, target) { for (let i = 0; i < nums.length; i++) { if (nums[i] === target) return i; } return -1;}def search(nums, target): for i in range(len(nums)): if nums[i] == target: return i return -1It ignores the sorting completely. In the worst case (target missing, or at the very end) it looks at every item: 7 looks for 7 items, 1,000,000 looks for a million items. That’s O(n): the work grows in a straight line with the input. Not terrible, but the problem asks for O(log n), which for a million items is about 20 looks.
Binary search keeps a range lo..hi (two indexes, “low” and “high”) where
the target must be if it exists. Each round it checks the middle index mid
and moves lo or hi past it, cutting the range in half.
A promise that stays true on every trip around a loop is called a loop invariant. It’s how you convince yourself (and your interviewer) that the code is right.
Pattern
Classic binary search
Use it when: the data is sorted (or has a yes/no answer that flips only once) and you need to find something faster than reading it all.
Signal words
- “sorted array”
- “O(log n)”
- “find the index”
- “search”
- “first / last position”
- Set
lo = 0andhi = nums.length − 1: the whole array is still possible. - While
lo <= hi(the range has at least one item): - Compute the middle:
mid = lo + (hi − lo) // 2(rounded down). - If
nums[mid]equals the target, returnmid. - If
nums[mid]is smaller, the target is to the right:lo = mid + 1. - If
nums[mid]is bigger, the target is to the left:hi = mid − 1. - If the loop ends, the range is empty: return
-1.
Press Play. The shaded block is lo..hi, the part still in play. Watch it
shrink by half every round, and the thrown-away parts fade out. In Not found,
watch lo and hi cross at the end: that’s the loop’s exit.
Binary search: halve the range each round
nums = [1, 3, 5, 7, 9, 11, 13], target = 11
- 10
- 31
- 52
- 73
- 94
- 115
- 136
- target
- 11
- lo
- 0
- hi
- 6
- mid
- —
- nums[mid]
- —
- items left
- 7hi − lo + 1
- rounds
- 0
- result
- —
- Still possible (lo..hi)
- mid, being checked
- Thrown away
- Target
- Not the target
We look for 11. If it's anywhere, it's somewhere in nums[lo..hi]. At the start that's the whole array: lo = 0, hi = 6.
Which line is running?
function search(nums, target) { let lo = 0;Running now: let hi = nums.length - 1; // the target, if present, is in nums[lo..hi] while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { lo = mid + 1; // mid is too small: drop it and everything left of it } else { hi = mid - 1; // mid is too big: drop it and everything right of it } } return -1; // the range is empty: the target is not here}Classic binary search
function search(nums, target) { let lo = 0; let hi = nums.length - 1; // the target, if present, is in nums[lo..hi] while (lo <= hi) { const mid = lo + Math.floor((hi - lo) / 2); if (nums[mid] === target) { return mid; } else if (nums[mid] < target) { lo = mid + 1; // mid is too small: drop it and everything left of it } else { hi = mid - 1; // mid is too big: drop it and everything right of it } } return -1; // the range is empty: the target is not here}def search(nums, target): lo, hi = 0, len(nums) - 1 # the target, if present, is in nums[lo..hi] while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid elif nums[mid] < target: lo = mid + 1 # mid is too small: drop it and everything left of it else: hi = mid - 1 # mid is too big: drop it and everything right of it return -1 # the range is empty: the target is not hereJavaScript sets lo and hi on two lines and has closing } lines, so its
line numbers run ahead of Python’s; we give both.
- Line 1: define the function. (LeetCode wraps it as
var search = function(nums, target), ordef search(self, nums, target)insideclass Solutionin Python.) - Lines 2–3 (JS) / line 2 (Py):
loandhistart at the first and last index, so the whole array is in play. Python can set both at once:lo, hi = 0, len(nums) - 1. - Line 4 (JS) / line 3 (Py):
lo <= himeans “the range has at least one item”. Whenlo == hithere is exactly one item left, and we must still check it, so it’s<=, not<. - Line 5 (JS) / line 4 (Py): the middle index.
(hi − lo) // 2is half the distance, rounded down (Math.floorin JS,//in Python). Adding it tololands in the middle. Writing(lo + hi) // 2gives the same number; thelo + (hi − lo) // 2form is a habit from languages like Java and C++, wherelo + hican be too big to store (an “overflow”). - Lines 6–7 (JS) / 5–6 (Py): found it. Return the index, not the value.
- Lines 8–9 (JS) / 7–8 (Py): the middle is too small. It and everything left of it are
ruled out, so
lojumps tomid + 1. The+ 1matters:midhas been checked. - Lines 10–11 (JS) / 9–10 (Py): the middle is too big, so
hijumps tomid − 1. - Line 14 (JS) / 11 (Py):
lo > hi: no candidates left. Return-1.
Trace nums = [1, 3, 5, 7, 9, 11, 13], target = 13. Each row is one round.
| round | lo | hi | mid | nums[mid] | compare | next |
|---|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 7 | 7 < 13 | lo = 4 |
| 2 | 4 | 6 | 5 | 11 | 11 < 13 | lo = 6 |
| 3 | 6 | 6 | 6 | 13 | 13 = 13 | return 6 |
Look at round 3: lo and hi are both 6, so the range has one item. The loop
still runs because the condition is lo <= hi. With lo < hi it would have
stopped one round early and missed the 13.
Now a missing target, nums = [-1, 0, 3, 5, 9, 12], target = 2:
| round | lo | hi | mid | nums[mid] | compare | next |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2 | 3 | 3 > 2 | hi = 1 |
| 2 | 0 | 1 | 0 | -1 | −1 < 2 | lo = 1 |
| 3 | 1 | 1 | 1 | 0 | 0 < 2 | lo = 2 |
| end | 2 | 1 | lo > hi | return −1 |
Linear search
Time
O(n)
Up to one look per item: a million items, a million looks.
Space
O(1)
One index variable.
Binary search
Time
O(log n)
Each round halves the range. A million items: 1,000,000 → 500,000 → … → 1 takes about 20 rounds.
Space
O(1)
Just lo, hi and mid.
log₂ n (“log base 2 of n”) answers: how many times can I halve n before I reach 1? 8 → 4 → 2 → 1 is 3 halvings, so log₂ 8 = 3. For 1,000 it’s about 10; for 1,000,000 about 20; for a billion about 30. Double the input, and binary search needs just one more round.
What to say out loud, in this order:
- “The array is sorted, so I can rule out half of it with one comparison.”
- State the invariant: “if the target exists, it’s in
nums[lo..hi].” - Explain the boundaries: “
lo <= hibecause a one-item range still needs checking;mid ± 1becausemidis already checked.” - Cost: O(log n) time, O(1) space; about 20 steps for a million items.
- Trace a one-item array and a missing target before saying you’re done.
Likely follow-up questions:
- “Find the first or last position of a repeated value?” When you find it, don’t return: record it and keep searching left (or right).
- “Where would the target be inserted?” When the loop ends,
lois exactly that index. - “Recursive version?” Same logic, with
loandhias parameters. It uses O(log n) space for the call stack.
Related problems:
- Search a 2D Matrix (this week): the same template on a grid.
- Find Minimum in Rotated Sorted Array (this week): binary search when the array isn’t fully sorted.
- Search in Rotated Sorted Array and Koko Eating Bananas (week 4): binary search on rotated data and “on the answer”.
- The week 3 overview has the template and an off-by-one survival guide.