Topic 5 / 16
Binary Search
MediumSearch~4 days
Easy to grasp
progress0 / 14 solved
Halve the search space each iteration. Works on sorted arrays and answer-space problems.
Prerequisites
Concept
Repeatedly halve the search space by comparing the target to the midpoint. Requires sorted input or a monotonic predicate. Classic binary search finds an exact value; generalized binary search finds the boundary where a condition flips from false to true. Binary search on answer treats the answer space as the array.
When to use this pattern
- ◆Array is sorted or has a monotonic property
- ◆Find minimum/maximum value that satisfies a condition
- ◆Search in rotated sorted array
- ◆Real-valued binary search (floating point answers)
- ◆Koko eating bananas / capacity ship packages style problems
Common patterns
Classic — find target
lo=0, hi=n-1. Return mid when arr[mid]==target.
Left boundary
Find first position where condition is true. Use lo=mid+1 when false.
Right boundary
Find last position where condition is true. Use hi=mid-1 when true.
Binary search on answer
Define a feasibility function; binary search the answer range.
Visual walkthrough
Binary search — target = 13
1
03
15
27
39
mid11
513
615
717
819
9lo=0mid=4hi=9arr[mid] < target → move lo right
step 1 / 4
Brute force → optimal thinking
Brute force
Linear scan through sorted array → O(n).
Observation
Sorted order lets us eliminate half the array at each comparison.
Optimization
lo/hi pointers. mid = lo + (hi - lo) / 2. Move the pointer that can't contain the answer.
Final complexity
O(log n) — search space halves every iteration.
Quick Recall Check
Why should you use lo + (hi - lo) / 2 instead of (lo + hi) / 2?
Binary search on the answer space requires what property of the feasibility function?
In a rotated sorted array, how do you determine which half is sorted?
Am I ready to move on?
Check each question you can answer confidently before moving to the next topic.
Progress is saved on this device