Sorting & SearchingBeginner
Binary Search
Repeatedly halve the search space to find a target or boundary in O(log n) time.
Problem: Binary Search in Sorted Array
Find target 9 in the sorted array [1, 3, 5, 7, 9, 11, 13].
M
1
3
5
7
9
11
13
L
R
Initialize: low=0, high=6, mid=3
Low=0, High=6, Mid=(0+6)/2=3. arr[3]=7. Compare 7 with target 9: 7 < 9, so target is in the right half. Move low to mid+1.
Low: 0Mid: 3High: 6< Too low
Step 1/4
Speed:
When to Use
- Sorted array search
- Find boundary (first/last occurrence)
- Search in rotated sorted array
- Minimize/maximize with monotonic property
Key Indicators
- Sorted array
- "Search", "find" in sorted data
- Monotonic property
- Minimize maximum / maximize minimum
Complexity
Time
O(log n)
Space
O(1)
Common Problems
Binary SearchSearch in Rotated Sorted ArrayFind First and Last PositionKoko Eating BananasCapacity To Ship Packages
Code
low, high = 0, n - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)