Binary search algorithms.
Find boundaries, uncover structure, and search the answer space.
Search & boundaries
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Binary Search | Easy | O(log n) | LeetCode |
| Lower Bound & Search Insert Position | Easy | O(log n) | — |
| Upper Bound | Easy | O(log n) | — |
| First & Last Occurrence | Medium | O(log n) | — |
Rotations & structure
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Search in a Rotated Sorted Array | Medium | O(log n) | — |
| Rotated Search with Duplicates | Medium | O(n) worst case | — |
| Minimum in a Rotated Sorted Array | Medium | O(log n) | — |
| Find a Peak Element | Medium | O(log n) | — |
| Single Element in a Sorted Array | Medium | O(log n) | — |
Numbers & matrices
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Integer Square Root | Easy | O(log x) | — |
| Exact Integer Nth Root | Medium | O(p log x) | — |
| Search a 2D Matrix | Medium | O(log(rc)) | — |
| Kth Smallest in a Sorted Matrix | Medium | O((r + c) log W) | — |
Search on the answer
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Koko Eating Bananas | Medium | O(n log M) | — |
| Capacity to Ship Packages Within D Days | Medium | O(n log S) | — |
| Split Array Largest Sum | Hard | O(n log S) | — |
| Minimum Days to Make Bouquets | Medium | O(n log M) | — |
| Aggressive Cows / Maximum Minimum Distance | Medium | O(n log n + n log W) | — |
Two-array partitions
| Problem | Difficulty | Time complexity | Practice |
|---|---|---|---|
| Median of Two Sorted Arrays | Hard | O(log(min(n, m) + 1)) | — |
| Kth Element of Two Sorted Arrays | Hard | O(log(min(n, m) + 1)) | — |