Binary Search Variants: Rotated Arrays & Search Space
You'll learn to
- -Search a rotated sorted array in O(log n) by identifying which half is properly sorted
- -Recognize "binary search on the answer" as a pattern applied to a range of candidate answers, not an array
Plain binary search from the last chapter assumed a fully sorted array from end to end. Real problems - and Level 6 - push further, into a rotated sorted array: a sorted array that has been cut at some pivot point and had its front chunk moved to the back.
Rotated Sorted Arrays
Consider [4, 5, 6, 7, 0, 1, 2], which is [0, 1, 2, 4, 5, 6, 7] rotated at index 4. Plain binary search breaks here, because comparing items[mid] against the target no longer reliably indicates which half to discard - the middle element is not guaranteed to sit between the array's two endpoint values anymore. The fix relies on one fact that always holds true, even after rotation: at least one of the two halves, left..mid or mid..right, is always properly sorted. Check which half is sorted by comparing its own endpoints, then check whether the target falls within that sorted half's value range - if it does, continue the search there; if not, the target must be in the other, still-rotated half.
Tracing search_rotated([4, 5, 6, 7, 0, 1, 2], 0): left = 0, right = 6, mid = 3, items[3] = 7. Since items[left] = 4 is less than or equal to items[mid] = 7, the left half is the sorted one; is 4 <= 0 < 7? No, so left becomes mid + 1 = 4. Next: left = 4, right = 6, mid = 5, items[5] = 1. Since items[left] = items[4] = 0 is less than or equal to items[mid] = 1, the left half [4..5] is sorted; is 0 <= 0 < 1? Yes, so right becomes mid - 1 = 4. Next: left = 4, right = 4, mid = 4, items[4] = 0 matches the target, returning index 4.
Binary Search on the Answer
Binary search does not actually require an array at all - it only requires a range of candidate answers, plus a feasibility check ("is this candidate good enough?") that is monotonic, meaning true for every value on one side of some cutoff and false on the other. Given both, the search happens over the RANGE of possible answers instead of over array indices, cutting the space in half on every check just the same. Classic examples include "what is the minimum possible maximum load if this array is split into k parts?" or "what is the smallest shipping capacity that delivers every package within d days?" - both are solved by binary searching over a numeric range of candidate answers, calling a feasibility-check function at each candidate. Whenever a problem seems to require trying every possible value from some low bound to some high bound, and checking a single candidate is cheap, that is the signal this pattern applies - it turns what looks like a linear scan into a logarithmic one, the same as searching an array does.
The tell that a problem wants binary search on the answer, rather than on data: it asks for a minimum or maximum value satisfying some condition, over a huge range of candidates, where checking one candidate is cheap but trying every candidate individually would be far too slow.
Why does plain binary search fail on a rotated sorted array without modification?
Level 6: Binary Search Mastery asks you to implement binary search plus a rotated-sorted-array variant - exactly the search_rotated function walked through above.