LeetCode · Binary Search
Binary Search Problem Set
Halve the search space every step. Classic sorted-array search, rotated arrays, and "search on answer" where you binary-search the result space.
Concept page:
Binary Search
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Easy | classic | LC 704 · Binary Search | Standard search in sorted array. O(log n). |
| Easy | boundary | LC 35 · Search Insert Position | Find insertion point (lower bound). O(log n). |
| Medium | bounds | LC 34 · Find First and Last Position of Element in Sorted Array | Combine lower bound and upper bound to get the full duplicate range in O(log n). |
| Medium | rotated | LC 33 · Search in Rotated Sorted Array | Determine which half is sorted, search accordingly. O(log n). |
| Medium | rotated | LC 153 · Find Minimum in Rotated Sorted Array | Binary search comparing mid to right boundary. O(log n). |
| Medium | peak | LC 162 · Find Peak Element | Move toward the higher neighbour. O(log n). |
| Medium | matrix | LC 74 · Search a 2D Matrix | Treat as flattened sorted array. O(log(m·n)). |
| Medium | search-on-answer | LC 875 · Koko Eating Bananas | Binary search on eating speed. Feasibility check per candidate. O(n log m). |
| Medium | search-on-answer | LC 1011 · Capacity To Ship Packages Within D Days | Binary search the minimum ship capacity whose greedy simulation finishes within the deadline. |
| Medium | design | LC 981 · Time Based Key-Value Store | Binary search on timestamps within each key's list. O(log n) per get. |
| Hard | divide | LC 4 · Median of Two Sorted Arrays | Binary search on the smaller array's partition. O(log min(m,n)). |