13. Binary Search
Lower/upper bound, rotated arrays and binary search on the answer.
🎬 Episodes 21–23: video coming soon
Your progress0 of 17
5easy
10medium
2hard
Understand the topic
Binary search cuts the search space in half each step, so a million items take about 20 steps. It doesn't really need a sorted array; it needs a yes/no question whose answers look like F F F T T T. Then you find the first T.
There are two flavours. First, searching an array (lower bound, rotated arrays, peaks). Second, "binary search on the answer": guess a value like a speed or a capacity, check whether it's feasible, and move the guess.
| # | Problem | Pattern | Level | ||
|---|---|---|---|---|---|
| 1 | Binary Search #704 | Classic binary search | Easy | LeetCode ↗ | |
| 2 | Search Insert Position #35 | Lower bound | Easy | LeetCode ↗ | |
| 3 | Sqrt(x) #69 | Binary search on the answer | Easy | LeetCode ↗ | |
| 4 | First Bad Version #278 | First true | Easy | LeetCode ↗ | |
| 5 | Kth Missing Positive Number #1539 | Binary search on a derived value | Easy | LeetCode ↗ | |
| 6 | Find First and Last Position of Element in Sorted Array #34 | Lower & upper bound | Medium | LeetCode ↗ | |
| 7 | Search in Rotated Sorted Array #33 | Find the sorted half | Medium | LeetCode ↗ | |
| 8 | Find Minimum in Rotated Sorted Array #153 | Compare with the right end | Medium | LeetCode ↗ | |
| 9 | Find Peak Element #162 | Follow the slope | Medium | LeetCode ↗ | |
| 10 | Single Element in a Sorted Array #540 | Pair parity | Medium | LeetCode ↗ | |
| 11 | Koko Eating Bananas #875 | Binary search on the answer | Medium | LeetCode ↗ | |
| 12 | Capacity To Ship Packages Within D Days #1011 | Binary search on the answer | Medium | LeetCode ↗ | |
| 13 | Minimum Number of Days to Make m Bouquets #1482 | Binary search on the answer | Medium | LeetCode ↗ | |
| 14 | Find the Smallest Divisor Given a Threshold #1283 | Binary search on the answer | Medium | LeetCode ↗ | |
| 15 | Magnetic Force Between Two Balls #1552 | Binary search on the answer (aggressive cows) | Medium | LeetCode ↗ | |
| 16 | Split Array Largest Sum #410 | Binary search on the answer (book allocation) | Hard | LeetCode ↗ | |
| 17 | Median of Two Sorted Arrays #4 | Binary search on the partition | Hard | LeetCode ↗ |
Nothing matches that filter.
Work top to bottom — each list goes from easy to hard. Try a problem for at least 15 minutes before opening a hint. Ticks are saved in your browser.