Binary Search
Halve the search space every step. Trace low, mid, and high as they converge on the target.
What is binary search?
An algorithm that finds a target in a sorted array by repeatedly cutting the search range in half. Instead of checking every element, it jumps to the middle and eliminates half of the remaining items each step.
Where you will see it
Real systems that use this exact idea. Tap a card to open it.
Common traps
The mistakes interviewers watch for. Guess the fix, then reveal it.
FixUse low <= high. With strict <, a single-element range [i, i] never gets checked and targets at the last position are missed.
FixAlways move past mid: low = mid + 1 or high = mid - 1. Keeping mid in the range causes infinite loops when the range narrows to two elements.
FixInteger overflow when low + high exceeds INT_MAX. Use low + (high - low) / 2 - the bug that lived unnoticed in JDK's own binary search for nine years.
Interview prep
Questions you could be asked, with the depth an interviewer wants to hear.
Only on sorted data. If the input is not sorted, the discard-half logic is invalid and the result is wrong.
O(log n) · requires sorted data
Real worldDatabase indexes and git bisect both rely on this precondition.
DeeperIf you need binary search on unsorted data, you pay the sort cost first.