The idea: eliminate half the possibilities every guess
Think about looking up a word in a physical dictionary. You don't start on page one and read every entry — you flip to the middle, see whether your word falls before or after, and instantly ignore half the book. Repeat on the half that remains and you close in on the word in a handful of flips. Binary search is that strategy written down precisely: given a sorted list, check the middle element. If it's your target, you're done. If your target is larger, it must be in the right half; if smaller, the left half. Either way you throw away half of what's left and repeat.
The power comes from that halving. A list of a million items is found in about 20 comparisons, a billion in about 30. This is exactly the part that becomes obvious when you watch it animate — the search window collapses shockingly fast.
The mechanics: two pointers and a shrinking window
Implementations track the live search range with two indices, usually called low and high, that bracket the portion of the array still in play. Each iteration computes the midpoint mid = (low + high) // 2 and compares nums[mid] to the target. On a match, return mid. If nums[mid] is too small, the target can only be to the right, so move low = mid + 1. If it's too big, move high = mid - 1. The loop continues while low <= high; when the pointers cross, the range is empty and the target isn't there.
Two details make or break the code. First, the + 1 and - 1 when updating the pointers: you've already checked mid, so excluding it guarantees the range shrinks and the loop terminates. Second, the loop condition low <= high — using < instead of <= either skips the final single-element range or loops forever. This is why binary search is famous as easy to describe and easy to get subtly wrong.
Why it's O(log n) — and the one precondition
Each comparison discards half the remaining elements, so the count goes n → n/2 → n/4 → … until one is left. The number of halvings needed to get from n down to 1 is log₂(n), and that is the running time: O(log n). Space is O(1) for the iterative version, since only the two pointers are stored; a recursive version uses O(log n) stack space.
The catch — and it is the whole catch — is that the data must be sorted. Binary search's entire logic rests on being able to say "everything to the right of mid is larger." On unsorted data that guarantee is gone and the answer is meaningless. If you only need to search once, sorting first (O(n log n)) usually isn't worth it over a plain linear scan; binary search pays off when the data is already sorted or you'll query it many times.
def binary_search(nums, target):
"""Return the index of target in sorted nums, or -1 if absent."""
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2 # midpoint of the current range
if nums[mid] == target:
return mid # found it
elif nums[mid] < target:
low = mid + 1 # discard the left half
else:
high = mid - 1 # discard the right half
return -1 # target not in the arrayBest case O(1) when the target is the first midpoint; worst and average case O(log n). The input must be sorted; the recursive form trades O(1) space for O(log n) call-stack space.
When to use it
- Checking whether a value exists (and where) in a large array that is already sorted.
- Finding a boundary — the first or last index of a value, or the correct insertion point that keeps an array sorted (lower/upper bound).
- 'Binary search on the answer': finding the smallest or largest value that satisfies a monotonic condition, like the minimum ship capacity or speed that still meets a deadline.
- Querying static, sorted data repeatedly, where an O(log n) lookup beats an O(n) scan on every request.
Watch out for
- Off-by-one bugs: mismatching the loop condition (<= vs <) with the pointer updates, or forgetting the ± 1, which causes infinite loops or a missed final element.
- Running it on unsorted data — the result is simply wrong, because the discard-a-half step assumes ordering.
- Integer overflow on (low + high) in fixed-width languages like Java or C++; use low + (high - low) // 2 instead. Python's arbitrary-precision integers avoid this.
Binary search is often the first \"real\" algorithm interviewers reach for, both as a standalone warm-up and as a building block inside harder problems. Beyond the textbook \"find x in a sorted array,\" expect variants: find the first or last occurrence of a value, search in a rotated sorted array, find a peak element, or \"binary search on the answer\" for optimization questions. Interviewers watch whether you state the sorted precondition up front, get the loop invariant and bounds exactly right (the off-by-one is where most candidates stumble), and can explain clearly why the running time is O(log n). Writing it bug-free on the first attempt and testing edge cases — empty array, single element, target absent, target at the ends — is what signals real fluency rather than a memorized template.