Linear search checks each element in turn — simple, O(n), and works on any data. Binary search repeatedly halves a sorted range, reaching the answer in O(log n). The catch, and the most common mistake, is forgetting that binary search requires sorted input.
Halve the search space
Binary search keeps a low and high boundary. Compare the middle element to the target: if it matches you are done; if the target is larger, discard the left half; if smaller, discard the right half. Each step throws away half the data.
Binary search
lo = 0; hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) / 2 // avoids overflow
if A[mid] == target: return mid
if A[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1O(log n)→O(1)
Each step halves the remaining range.
⚡ The edge
- Binary search needs sorted data — always check that first. Compute the midpoint as lo + (hi - lo)/2 to avoid integer overflow.
- It does far more than 'find x': it also finds the first/last occurrence, and the smallest value satisfying a condition — the 'binary search on the answer' pattern.
Worked example
Search for 7 in [1, 3, 5, 7, 9, 11]. Trace the steps.
- lo=0, hi=5, mid=2 -> A[2]=5, which is < 7, so search the right half: lo=3.
- lo=3, hi=5, mid=4 -> A[4]=9, which is > 7, so search the left half: hi=3.
- lo=3, hi=3, mid=3 -> A[3]=7, a match. Found at index 3 in 3 steps.
Answer: Found at index 3 (O(log n))
Worked example
Why does binary search fail on [4, 2, 7, 1, 9]?
- Binary search assumes that going right always means larger values.
- This array is unsorted, so comparing the middle tells you nothing about which half holds the target.
- You must sort first (O(n log n)) or use linear search (O(n)).
Answer: It requires sorted data; here it would give wrong results
⚠ Watch out
- Binary search only works on sorted data — the number-one mistake.
- Use lo + (hi - lo)/2 for the midpoint to avoid overflow on large indices.
- Watch the loop condition (lo <= hi) and the updates (mid+1 / mid-1) to avoid an infinite loop or skipping the answer.