Topic 6 of 20
Binary Search
Halve the search space each step, on arrays and, more powerfully, on the answer itself.
The concept
Binary search finds a target in a sorted range by repeatedly discarding half of it, giving O(log n) time. It sounds simple, but off-by-one errors make it one of the most commonly failed interview topics. Pick one template (for example lo < hi with hi = mid or lo = mid + 1), learn exactly what it returns (the first index where a condition becomes true), and use it every time.
The real power of binary search is that it works on any monotonic condition, not just sorted arrays. If "can we finish with speed x?" is false for small x and true for large x, you can binary search on x itself. This binary search on the answer pattern solves a large family of "minimise the maximum" and "find the smallest capacity" questions in O(n log range).
You will also meet rotated arrays (one half is always sorted, so decide which half to keep), 2D matrices treated as 1D, and the famous median-of-two-sorted-arrays partition trick.
Patterns you will learn
- Classic Binary Search
- Lower / Upper Bound
- Rotated Sorted Array
- Binary Search on Answer
- Binary Search on Two Arrays
Problems, in order
- 1Binary SearchEasy
Nail one bug-free template before anything else.
Classic Binary SearchReported at: AmazonAppleGoogle+5 - 2
Lower bound: the first index whose value is ≥ target.
Lower / Upper BoundReported at: AmazonAppleGoogle+6 - 3
Binary search over a boolean predicate, the foundation of search-on-answer.
Lower / Upper BoundReported at: GoogleAmazonMeta+4 - 4Sqrt(x)Easy
Searching over the answer space instead of an array.
Binary Search on AnswerReported at: AmazonAppleGoogle+4 - 5
An interactive-API variant that forces careful boundary updates.
Classic Binary SearchReported at: AdobeBloomberg - 6
- 7
Lower and upper bound together; very frequently asked.
- 8Search a 2D MatrixMedium
Treat a matrix as a flattened sorted array.
Classic Binary SearchReported at: MetaAmazonMicrosoft+7 - 9Search a 2D Matrix IIMedium
Start at a corner and eliminate a row or column per step.
Staircase SearchReported at: AmazonMicrosoftMeta+3 - 10
- 11
Minimise a capacity subject to a feasibility check.
- 12
Search on days, checking contiguous groups.
Binary Search on AnswerReported at: Google - 13
Sort once, then binary search per query.
- 14
Compare with the right end to find the pivot.
Rotated Sorted ArrayReported at: AmazonMetaMicrosoft+4 - 15
Decide which half is sorted; one of the most-asked Mediums.
Rotated Sorted ArrayReported at: AmazonMetaMicrosoft+15 - 16Find Peak ElementMedium
Binary search without sorted data, guided by the slope.
Binary Search on SlopeReported at: MetaAmazonGoogle+4 - 17
Uses index parity to decide which side is broken.
Binary Search on Index ParityReported at: AmazonMetaMicrosoft+3 - 18
A design question whose core is upper-bound search.
Upper Bound on TimestampsReported at: AmazonMicrosoftGoogle+2 - 19Find K Closest ElementsMedium
Binary search for the left edge of the best window.
Binary Search on Window StartReported at: MetaGoogleAmazon+4 - 20
Counting elements ≤ mid across a sorted matrix.
Binary Search on ValueReported at: MetaAmazonGoogle+5 - 21
The famous O(log(min(m,n))) partition problem.
Binary Search on PartitionReported at: AmazonAppleMicrosoft+10 - 22
Minimise the maximum subarray sum; a classic Hard.
Binary Search on AnswerReported at: GoogleAmazonMeta+2 - 23
Composes three binary searches under an API-call limit.
- 24
Counting under a formula without building the table.
- 25
Combines search on answer with a two-pointer count.
Binary Search on Answer + Two PointersReported at: Meta