The Core Idea
Guessing a Number Between 1 and 100
If someone picks a number between 1 and 100 and you can only ask 'higher or lower,' the smart strategy isn't guessing 1, then 2, then 3. It's guessing 50 first. Whatever the answer, you've just eliminated half the possibilities in one question. Guess 75 or 25 next, and you eliminate half of what's left. This is binary search — and it's why you can find that number in at most 7 guesses instead of up to 100.
Binary search only works on sorted data. Without order, there's no way to know which half to eliminate — that's the one hard prerequisite that trips people up.
💡 Memory Trick
Remember the three pointers as a phone book you're flipping through: LOW is the earliest page you'd still check, HIGH is the latest page you'd still check, and MID is the page you flip to right now — always exactly in the middle of low and high. After checking mid, you either move LOW up past it or HIGH down past it, shrinking your search zone in half every time.
The Algorithm
The Step-by-Step Mechanics
1
Set Low and High
Start with low = 0 (the first index) and high = length - 1 (the last index). These two pointers define the entire range you still need to search.
Example: for a 10-item array, low = 0, high = 9.
2
Calculate Mid
Find the middle index: mid = (low + high) / 2, rounding down. This is the single element you'll check on this pass.
Example: low = 0, high = 9 → mid = 4.
3
Compare and Eliminate Half
If the target equals arr[mid], you're done — return mid. If target is smaller than arr[mid], the answer must be in the left half, so set high = mid - 1. If target is larger, the answer must be in the right half, so set low = mid + 1.
Example: if target < arr[4], set high = 3, discarding indices 4–9 entirely.
4
Repeat Until Found or Exhausted
Keep recalculating mid within the shrinking low-to-high range. If low ever exceeds high, the target isn't in the array — return 'not found.' Each pass halves the search space, which is exactly why the total number of passes is log₂(n).
Why It's Fast
The Halving Effect at Scale
This is the concrete reason binary search is O(log n): a linear scan of 1,000,000 sorted items could take up to 1,000,000 comparisons in the worst case, but binary search takes at most about 20 — because 2²⁰ is roughly 1,000,000. Each comparison doubles the size of the array you could handle in the same number of steps.
This is also why binary search shows up constantly beyond simple arrays — it's the backbone of searching in binary search trees, finding insertion points in sorted structures, and even solving optimization problems where you binary search over a range of possible answers rather than over an array.
🖥️ Applied Scenario
You're given a sorted array of 1,000 exam scores and asked to find whether the score 87 exists in it, using the fewest comparisons possible.
1
You set low = 0 and high = 999, then compute mid = 499 and check the score there.
2
If arr[499] is greater than 87, you know 87 (if it exists) must be to the left, so you set high = 498 and recompute mid.
3
You repeat this process, and within about 10 comparisons — instead of scanning all 1,000 scores — you either land exactly on 87 or exhaust the range and confirm it isn't present.
4
Conclusion: because the array was sorted, you turned a potential 1,000-step search into roughly 10 steps by halving the search space every time.
📌 Exam Application
Exam questions frequently test the off-by-one details: whether high starts at length-1 or length, whether the loop condition is low <= high or low < high, and whether mid is recalculated as (low+high)/2 or low + (high-low)/2 to avoid integer overflow in some languages. Also expect questions asking you to state binary search's complexity (O(log n)) and to explain why it requires sorted input.
⚠️ Most Common Binary Search Mistakes
The most common mistake is running binary search on unsorted data — it will silently return wrong answers rather than erroring, because the halving logic assumes order that isn't there. Another frequent error is forgetting to update low or high correctly (using mid instead of mid+1 or mid-1), which can cause an infinite loop when low and high converge on the same value without ever properly narrowing.
✓ Quick Self-Test
Can you trace through binary search by hand on a 15-element sorted array to find a specific value, writing down low, mid, and high at every step? Can you explain in one sentence why binary search cannot be used on an unsorted array?
Next Lesson
Sorting Algorithms
→
← All Algorithms Lessons