Binary Search Variants: Rotated Arrays & Search Space

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.

Imagine a long scroll with names in alphabetical order, cut at one point, with the two pieces swapped, so the end of the alphabet now comes first. Each piece is still in perfect order on its own; the break is only at the join. If you open the scroll in the middle, you cannot tell from one name alone which way to go, but you can tell which side of your cut is the clean, ordered stretch.

• -Each intact piece is a properly sorted half.
• -The join between the pieces is the pivot, where the order breaks.
• -Opening the scroll in the middle is checking items[mid].

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 says which half to discard. The middle element is no longer guaranteed to sit between the two endpoint values.

The fix relies on one fact that survives rotation: at least one of the two halves, left to mid or mid to right, is always properly sorted. That gives a three-step recipe:

• -Find the sorted half by comparing its own two endpoints.
• -Check whether the target lies inside that sorted half's range of values.
• -If it does, search that half. If not, the target can only be in the other half.

• -left = 0, right = 6, mid = 3, items[3] = 7. Since items[0] = 4 is at most 7, the left half is the sorted one. Is 4 <= 0 < 7? No, so left = mid + 1 = 4.
• -left = 4, right = 6, mid = 5, items[5] = 1. Since items[4] = 0 is at most 1, the left half [4..5] is sorted. Is 0 <= 0 < 1? Yes, so right = mid - 1 = 4.
• -left = 4, right = 4, mid = 4, and items[4] = 0 equals the target. Return index 4.

One caveat is worth saying in an interview. The test items[left] <= items[mid] stops being a reliable way to find the sorted half when the array has duplicates. For example, search_rotated([1, 0, 1, 1, 1], 0) returns -1 even though 0 is at index 1, because items[left], items[mid] and items[right] are all 1 and the test cannot tell which side holds the break. With duplicates the worst case degrades to O(n), and a correct solution needs a step that shrinks the range by one when the endpoints are equal.

Binary search does not actually need an array. It needs a range of candidate answers and a yes-or-no feasibility check that is monotonic: false for every candidate below some cutoff and true from the cutoff upward (or the other way round).

The search then halves the range of candidate answers, not the array indices, in exactly the same way. Classic examples are the minimum possible maximum load when an array is split into k parts, or the smallest shipping capacity that delivers every package within d days.

Take the shipping problem: packages weigh [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and must go in order, with at most 5 days, one trip a day. What is the smallest daily capacity? The answer must be at least 10 (the heaviest package) and at most 55 (everything in one day), so there are 46 candidates. A feasibility check is cheap: pack packages greedily and count the days.

The answer is 15, found in about 6 feasibility checks (log2 of 46, rounded up) instead of trying all 46 candidates. If an answer range is in the billions, the difference is between 30 checks and a billion.