Binary Search problems, grouped by pattern
Binary search works on anything with a sorted or monotonic shape, not just sorted arrays. Once bisect_left and bisect_right are second nature, rotated arrays, 2D matrices and "minimum speed that works" problems all use the same loop.
When to reach for it
- The input is sorted or rotated
- Checking one candidate answer is easy, finding it is hard
- The constraints hint at O(log n)
Mistakes to watch for
- Infinite loops from mid rounding
- Mixing inclusive and exclusive bounds
- Overflow in (lo + hi) / 2 in Java
The 25 problems
1Basics
- Fundamentals Animated Easy
- Binary Search Animated Easy
2Bisect
- bisect_left, bisect_right Animated Easy
- Search Insert Position Animated Easy
- Floor in a Sorted Array Animated Easy
- Ceil in a Sorted Array Animated Easy
- Find First and Last Position of Element in Sorted Array Animated Medium
- Number of occurrence Animated Easy
3Unique 1-D Binary Search
- First Bad Version Animated Easy
- Single Element in a Sorted Array Animated Medium
- Find Peak Element Animated Medium
4Rotated Array
- Find How Many Times Array is Rotated Animated Easy
- Find Minimum in Rotated Sorted Array Animated Medium
- Find Minimum in Rotated Sorted Array II Animated Hard
- Search in Rotated Sorted Array Animated Medium
- Search in Rotated Sorted Array II Animated Medium
52D Binary Search + Step Search
- Row with max 1s Animated Medium
- Search a 2D Matrix Animated Medium
- Search a 2D Matrix II (Young Tableau) Animated Medium
6Search on Answer Range
- Pow(x, n) (Binary Exponentiation) Animated Medium
- Find Nth root of M Animated Easy
- Sqrt(x) Animated Easy
- Find position of an element in a sorted array of infinite numbers (Galloping Search) Animated Medium
7Binary Search on Answer Space
- Koko Eating Bananas Animated Medium
- Minimum Number of Days to Make m Bouquets Animated Medium