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 47 problems
1Basics
- Fundamentals Animated Easy
- Binary Search Animated Easy
- Time Based Key-Value Store Medium
- Random Pick with Weight Medium
- Snapshot Array Medium
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
- Find Smallest Letter Greater Than Target Easy
- Online Election Medium
- Find K Closest Elements Medium
- Most Beautiful Item for Each Query Medium
- Heaters Medium
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
- Leftmost Column with at Least a One 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
- Separate Squares I Medium
- Magnetic Force Between Two Balls Medium
- Minimize Max Distance to Gas Station Hard
- Split Array Largest Sum Hard
- Maximum Number of Tasks You Can Assign Hard
- Minimum Limit of Balls in a Bag Medium
- Kth Smallest Element in a Sorted Matrix Medium
- Maximum Tastiness of Candy Basket Medium
- Smallest Good Base Hard
- Capacity To Ship Packages Within D Days Medium
- Kth Smallest Number in Multiplication Table Hard
- Reach a Number Medium