Skip to content

Topic 6 of 20

Binary Search

Halve the search space each step, on arrays and, more powerfully, on the answer itself.

25 problems6 Easy14 Medium5 Hard

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

Problems, in order

  1. 1

    Nail one bug-free template before anything else.

    Classic Binary SearchReported at: AmazonAppleGoogle+5
  2. 2

    Lower bound: the first index whose value is ≥ target.

    Lower / Upper BoundReported at: AmazonAppleGoogle+6
  3. 3

    Binary search over a boolean predicate, the foundation of search-on-answer.

    Lower / Upper BoundReported at: GoogleAmazonMeta+4
  4. 4

    Searching over the answer space instead of an array.

    Binary Search on AnswerReported at: AmazonAppleGoogle+4
  5. 5

    An interactive-API variant that forces careful boundary updates.

    Classic Binary SearchReported at: AdobeBloomberg
  6. 6

    Monotonic formula check, with an O(1) math alternative.

  7. 7

    Lower and upper bound together; very frequently asked.

  8. 8

    Treat a matrix as a flattened sorted array.

    Classic Binary SearchReported at: MetaAmazonMicrosoft+7
  9. 9

    Start at a corner and eliminate a row or column per step.

    Staircase SearchReported at: AmazonMicrosoftMeta+3
  10. 10

    The textbook search-on-answer problem.

  11. 11

    Minimise a capacity subject to a feasibility check.

  12. 12

    Search on days, checking contiguous groups.

    Binary Search on AnswerReported at: Google
  13. 13

    Sort once, then binary search per query.

  14. 14

    Compare with the right end to find the pivot.

    Rotated Sorted ArrayReported at: AmazonMetaMicrosoft+4
  15. 15

    Decide which half is sorted; one of the most-asked Mediums.

    Rotated Sorted ArrayReported at: AmazonMetaMicrosoft+15
  16. 16

    Binary search without sorted data, guided by the slope.

    Binary Search on SlopeReported at: MetaAmazonGoogle+4
  17. 17

    Uses index parity to decide which side is broken.

    Binary Search on Index ParityReported at: AmazonMetaMicrosoft+3
  18. 18

    A design question whose core is upper-bound search.

    Upper Bound on TimestampsReported at: AmazonMicrosoftGoogle+2
  19. 19

    Binary search for the left edge of the best window.

    Binary Search on Window StartReported at: MetaGoogleAmazon+4
  20. 20

    Counting elements ≤ mid across a sorted matrix.

    Binary Search on ValueReported at: MetaAmazonGoogle+5
  21. 21

    The famous O(log(min(m,n))) partition problem.

    Binary Search on PartitionReported at: AmazonAppleMicrosoft+10
  22. 22

    Minimise the maximum subarray sum; a classic Hard.

    Binary Search on AnswerReported at: GoogleAmazonMeta+2
  23. 23

    Composes three binary searches under an API-call limit.

  24. 24

    Counting under a formula without building the table.

  25. 25

    Combines search on answer with a two-pointer count.