Binary Search
Boundaries, peaks, rotated arrays and searching on the answer.
5 notes · 26 min total
Questions0 of 36 done
Warm up with these before Phase 1.
Patterns
- 1Binary Search BoundariesExact match, first and last occurrence, floor and ceiling: pick the loop condition and read the answer from where the pointers stop.6 min
- 2Tipping Point & PeakUse the l < r squeeze to find where a condition flips (a peak, the single element, the first true) by comparing mid with a neighbor.4 min
- 3Binary Search on the AnswerWhen you must minimize or maximize a number, guess it, check feasibility with a yes/no function, and binary search the guesses.7 min
- 4Rotated Sorted ArraysSearch a rotated sorted array by comparing mid with the right end to find the half that is still sorted.4 min
- 5Searching 2D MatricesSearch sorted matrices by flattening them to 1D, by staircase elimination from a corner, or by binary searching the value range.5 min