Binary Search
Halve the range each step by comparing to the middle.
Binary Search Trace
Problem
Given an array of distinct integers sorted in ascending order, determine the index of a specified target value. Return the target's index when it appears; otherwise return -1.
Examples
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Input: nums = [2, 4, 7, 11, 15], target = 6
Output: -1
The Goal
nums is sorted in ascending order. Return the index of target, or -1 if it isn't there, in O(log n) time.
For [-1, 0, 3, 5, 9, 12] and target = 9, the answer is 4.
A scan checks every number. Binary search checks the middle and throws half away each time.
Halve what's left
Look at the middle of the range still in play. Sorted order tells you which half the target can't be in.
Each look drops half.
Key Idea: The Middle Rules Out a Half
Keep lo and hi, the ends of the range that could still hold the target. Look at mid, halfway between.
If nums[mid] is the target, you're done. If it's smaller, so is everything left of it, and lo moves to mid + 1. If it's larger, hi moves to mid - 1.
When lo passes hi, nothing is left, and the target isn't there.
The target is right of mid, so lo = mid + 1.
3 < 9, so lo = 3
The Algorithm
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1lo + (hi - lo) // 2 is the same as (lo + hi) // 2, but in languages with fixed-size integers it can't overflow.
| Range | Loop | Left move | Right move |
|---|---|---|---|
| Closed: lo to hi | while lo <= hi | lo = mid + 1 | hi = mid - 1 |
| Half-open: lo up to hi | while lo < hi | lo = mid + 1 | hi = mid |
Walkthrough
Run it on [-1, 0, 3, 5, 9, 12] with target = 9.
The first middle is index 2, holding 3. 3 is less than 9, so indices 0 to 2 are out and lo moves to 3. The next middle is index 4, holding 9: return 4.
Two looks, where a scan needs five. Try a missing target on the stage and watch lo pass hi.
Checkpoint · predict the next step
Step 2 of 5 on the stage: mid = 0 + (5 − 0) // 2 = 2, and nums[2] is 3.
lo on -1 (index 0) · hi on 12 (index 5) · mid on 3 (index 2) · target 9 · nums[mid] 3
Pitfalls
- Loop while
lo <= hi. With<, the last number left is never checked. - Move past
mid:mid + 1ormid - 1. Settinglo = midcan loop forever on two numbers. - With repeats, it returns one matching index, not always the first.
- The array has to be sorted. Otherwise the half it drops might hold the target.
lo = 3 and hi = 3. What should the loop do?
Complexity
Each look halves the range, so n numbers take at most about log₂ n + 1 looks. A million numbers need 20. That's O(log n) time, with O(1) extra space for lo, hi and mid.
Halve the range each look
- Each lookOne comparison.O(1)
- Number of looksThe range halves each time.dominantO(log n)
- Boundslo, hi and mid.O(1)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(log n) | 3 | 7 | 10 | 13 |
| O(n) | 10 | 100 | 1K | 10K |
About 20 looks for a million numbers.
In short
Keep [lo, hi] bounds and inspect the midpoint. If it equals the target you're done; if it's smaller search the right half, otherwise the left. Use lo + (hi − lo) / 2 for the midpoint and a consistent boundary convention to avoid infinite loops.
Common mistake
Computing mid as (lo + hi) / 2 (can overflow) or mismatching the loop condition with how you update lo/hi.