Pattern 2: Modified binary search (rotated array)
What if someone took the sorted array and rotated it at some arbitrary point?
[0,1,2,4,5,6,7]becomes[4,5,6,7,0,1,2]. You can still keep the O(log n) — the trick is to figure out, at each step, which half is still sorted.
Try it first: Search in Rotated Sorted Array
Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.
A sorted array was rotated at some unknown pivot (e.g., [0,1,2,4,5,6,7] became [4,5,6,7,0,1,2]). Given nums and target, return the index of target or -1. O(log n) is expected.
Example: nums = [4,5,6,7,0,1,2], target = 0 → 4.
Tried it? The easy way out is to scan everything — O(n) — and ignore that the array is "almost sorted". The theory below recovers the O(log n) even with the rotation.
The theory: one of the halves is always sorted
Here's the observation that unlocks everything: no matter how much the array
has been rotated, when you cut at mid, at least one of the two halves is
perfectly sorted. Always. (The other one contains the "turning point".)
You figure out which by comparing the ends:
- If
nums[left] <= nums[mid], the left half[left..mid]is sorted. - Otherwise, the right half
[mid..right]is sorted.
And then the clever bit: in the sorted half, you know exactly which values
it contains — so you can test whether target falls in it. If it does, go to
that half; if not, go to the other one. Either way, you discard half — and
O(log n) survives.
mid = middle
if nums[mid] == target → found
if the LEFT half is sorted (nums[left] <= nums[mid]):
if target is in [nums[left], nums[mid]) → go left
else → go right
else (the RIGHT half is sorted):
if target is in (nums[mid], nums[right]] → go right
else → go left
Watch the decision happen — notice how the active interval jumps to the side where the target can be:
Why does it stay O(log n)?
The structure is the same as classic binary search: each iteration does O(1) work (a few comparisons) and discards half of the interval. The number of iterations is still log₂(n). The rotation only changes how we decide the side — not how many times we cut. O(log n) time, O(1) space.
Example 2 — Find Minimum in Rotated Sorted Array
"What's the smallest element of the rotated array?" The smallest is the
turning point (the place where the order "breaks"). Same philosophy, an
even simpler decision: compare nums[mid] with nums[right].
- If
nums[mid] > nums[right], the turning point is to the right ofmid→ the minimum is in[mid+1 .. right]. - Otherwise,
midcould still be the minimum →[left .. mid].
Notice that here we use left < right and right = mid (without the −1):
we're converging on a position (the minimum), not testing an exact value
— a different flavor of binary search. These boundary details are what you
drill until they become reflex.
The lesson that generalizes
Binary search doesn't require a fully sorted array — it only requires that, at each step, you can decide with certainty which way to go. In the rotated array, the sorted half gives you that certainty. Whenever you can answer "is the target on this side or the other?" in O(1), binary search is on the menu.
🧠 Review quiz
0/41. When you cut a rotated array in the middle, what is ALWAYS true about the two halves?
2. How do you know which half is sorted in the rotated array?
3. Why does search in the rotated array stay O(log n)?
4. What is the general condition for being able to use binary search, even without the array being fully sorted?
Summary
- In a rotated array, one of the halves is always sorted; find which by comparing the ends and decide the side from there.
- O(log n) holds: the rotation changes the decision, not the number of cuts.
- Find Minimum: converge on the position of the turning point
(
left < right,right = mid). - Binary search only requires deciding the side with certainty in O(1) — not total order.
The section's second module starts now: bits. Next lesson, the fundamentals.