Classic binary search
In one line
In a sorted array, compare the target with the middle element and throw away the half that cannot contain it, so you find any value in O(log n) steps.
What it is
Binary search finds a value in a sorted collection by repeatedly checking the middle element. If the middle is too small, the answer can only be to the right; if it is too large, only to the left. Each comparison halves the remaining search space.
Because the range halves every step, an array of 1,000,000 items needs at most about 20 comparisons (2 to the power 20 is about one million), compared with up to 1,000,000 for a linear scan. The one hard requirement is order: the data must be sorted, or more generally the yes/no question you ask must flip only once across the range.
Why interviewers ask
Binary search looks easy but is famously easy to get wrong: off-by-one errors, infinite loops and wrong loop conditions. Interviewers use it to check that you can define a search range precisely, keep a loop invariant and test edge cases (empty array, one element, target missing, target at either end). It is also the base for harder problems such as bounds, rotated arrays and searching on the answer.
How it works
- 1Set lo = 0 and hi = n - 1. The invariant is: if the target exists, its index is inside [lo, hi].
- 2While lo <= hi (the range is not empty), compute mid = lo + (hi - lo) // 2.
- 3If nums[mid] equals the target, return mid.
- 4If nums[mid] is smaller than the target, everything at or left of mid is too small, so set lo = mid + 1.
- 5If nums[mid] is larger than the target, everything at or right of mid is too large, so set hi = mid - 1.
- 6If the loop ends because lo > hi, the range is empty and the target is not present: return -1. Each step removes at least half the range, so there are at most about log2(n) + 1 iterations.
Worked example · Find 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
- Step 1: lo = 0, hi = 9, mid = 4, nums[4] = 16. 16 < 23, so the target is right of index 4: lo = 5.
- Step 2: lo = 5, hi = 9, mid = 7, nums[7] = 56. 56 > 23, so the target is left of index 7: hi = 6.
- Step 3: lo = 5, hi = 6, mid = 5, nums[5] = 23. Found at index 5 after 3 comparisons.
- Searching for 24 instead: steps 1 to 3 are the same until nums[5] = 23 < 24 gives lo = 6; then mid = 6, nums[6] = 38 > 24 gives hi = 5. Now lo = 6 > hi = 5, the range is empty, return -1.
Picture it
Guessing a number between 1 and 100 when someone says 'higher' or 'lower': you guess 50, then 25 or 75, and so on. You never need more than 7 guesses, because each answer rules out half of what is left.
Reference code
def binary_search(nums, target):
"""Return the index of target in sorted nums, or -1."""
lo, hi = 0, len(nums) - 1 # search space is [lo, hi]
while lo <= hi: # stop when the range is empty
mid = lo + (hi - lo) // 2 # avoids overflow in fixed-width languages
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # target can only be to the right
else:
hi = mid - 1 # target can only be to the left
return -1
The closed range [lo, hi] always contains the target if it exists. Moving to mid + 1 or mid - 1 guarantees the range shrinks every iteration, so the loop cannot run forever. Time O(log n), extra space O(1).
Key patterns
Exact match
When: Sorted array, find whether a value exists or where it is
How: Closed range [lo, hi], loop while lo <= hi, return mid on equality, move lo = mid + 1 or hi = mid - 1.
First or last position (bounds)
When: Duplicates exist, or you need the insert position
How: Do not stop on equality; keep shrinking toward the boundary. See lower and upper bound.
Monotonic yes/no question
When: Any condition that is false, false, ..., true, true over a range
How: Binary search for the first true. The array does not have to exist: you can search over numbers (search on the answer).
Peak finding
When: Find any local peak in an array where neighbours differ
How: Compare nums[mid] with nums[mid + 1]: if it is rising, a peak exists to the right; otherwise one exists at mid or to the left.
Real-world use
Standard libraries
Java's Arrays.binarySearch, C++ std::binary_search and Python's bisect module all implement binary search over sorted arrays so application code never needs a linear scan of sorted data.
Database indexes
A B-tree index in PostgreSQL or MySQL InnoDB keeps keys sorted inside each page; finding a key means binary searching within a page, then following one child pointer down, so a lookup touches only a few pages even for millions of rows.
git bisect
git bisect finds the commit that introduced a bug by testing the middle commit of a range and discarding the half that is known good or known bad, so 1,000 commits need about 10 test runs.
Sorted lookup tables
Things like IP-to-country tables or tax brackets are stored as sorted ranges; a service binary searches the sorted range starts to find which range a value falls in, in microseconds.
In a project
A logistics app stores 2 million delivery events per day in a file sorted by timestamp. Support staff need to jump to 'what happened at 14:32' quickly, and the current tool scans the whole file, taking several seconds.
- Keep the events sorted by timestamp (they already arrive in time order) and load the timestamps into an array, or read fixed-size records directly from the file.
- Binary search the timestamp array for the requested time instead of scanning from the start.
- Test the edge cases explicitly: a time before the first event, after the last event, and exactly equal to an event.
- Measure the lookup before and after with the same queries.
Impact: Each lookup drops from about 2 million comparisons to about 21, so answers go from seconds to well under a millisecond, and the tool can now power an interactive time slider.
Trade-offs
Use it when
- The data is sorted and you need many lookups
- Random access by index is O(1) (arrays, not linked lists)
- A yes/no condition is monotonic over the search range
Avoid it when
- The data is unsorted and you only search once: sorting costs O(n log n), more than one O(n) scan
- You need average O(1) lookups on exact keys and do not need order: use a hash set or hash map
- The data structure has no random access, such as a linked list, where reaching the middle costs O(n)
Cost: Time O(log n), extra space O(1) iterative (O(log n) stack if written recursively). Sorting first costs O(n log n).
Common mistakes
- Mixing range conventions: using hi = n with while lo <= hi reads past the end of the array.
- Writing lo = mid or hi = mid with a closed range, which can loop forever when lo and hi are next to each other.
- Forgetting that the input must be sorted, or binary searching data sorted by a different key.
- Not testing an empty array, a single element, and a target smaller than the first or larger than the last element.
- Computing (lo + hi) / 2 in Java or C++ with large indexes, which can overflow; lo + (hi - lo) / 2 is safe.
Interview questions
Quick revision
- Requirement: sorted data, or a condition that flips once (monotonic).
- Closed range: lo = 0, hi = n - 1, while lo <= hi, lo = mid + 1, hi = mid - 1.
- mid = lo + (hi - lo) // 2 avoids overflow in Java and C++.
- Time O(log n): 1 million items need about 20 comparisons; 1 billion about 30.
- Space O(1) iterative, O(log n) recursive.
- Test: empty, one element, first, last, missing, duplicates.
- Sorting first costs O(n log n): only worth it for repeated searches.
Check yourself
1. At most how many comparisons does binary search need to find a value in a sorted array of 1,000,000 elements?
2. With lo = 0, hi = n - 1 and while lo <= hi, what should happen when nums[mid] < target?
3. Why is binary search a poor fit for a singly linked list?
4. You search for 7 in [1, 3, 5, 9, 11]. What does the classic algorithm return?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.