Rotated Lists: Which Half Is Sorted?
A radio station keeps its track numbers in sorted order, but tonight's playlist was started part-way through and wrapped around: [15, 18, 2, 5, 9, 12]. It is still almost sorted, just cut in one place and turned. Binary search seems ruined, because the middle item no longer tells you which side is bigger. It is not ruined, only in need of one extra question.
The rule
Cut a rotated list anywhere: one half is always sorted — test that half.
A rotated list has at most one "drop", the point where a big value is followed by a small one. When you split it at mid, the drop lands in at most one half, so the other half is a clean sorted run. You can tell which by comparing its ends: if nums[lo] <= nums[mid], the left half has no drop. On a sorted run, "is the target inside?" is a simple range check, and the answer tells you which half to keep.
def find_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1 # target is inside it
else:
lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Each check still throws away half the window, so the cost stays about log n. The method assumes distinct values; the drills show what repeats do to it.
Why compare nums[lo] with nums[mid] instead of hunting for the drop directly? Finding the drop needs a search of its own, which the next lesson builds. This one comparison answers "which half is clean?" in a single step, which is what keeps the whole search at about log n.
The shortcut
At each middle, ask two questions in a fixed order: "Which half is clean?" then "Is the target in the clean half's range?" Yes means go there; no means go to the other half. You never reason about the messy half directly.
Middle at position 2, value 2
Is the left half clean?
nums[0]is 15, bigger than 2, so no: the drop is on the left, and the right half, 2 to 12, is sorted.
The trap is reasoning about the half with the drop in it. Its values wrap around, so a range check there gives wrong answers. Always test the clean half.
Drills
Answer fast — trust the rule.
In [40, 50, 60, 10, 20, 30] with lo = 0, hi = 5 and mid = 2, which half is sorted?
What does find_rotated([40, 50, 60, 10, 20, 30], 35) return?
In [15, 18, 2, 5, 9, 12] the middle is position 2, value 2. How do you know the right half is sorted?
What does find_rotated([1, 3, 1, 1, 1], 3) return?
Remember
- Cut a rotated list anywhere: one half is always sorted — test that half.
- Shortcut: which half is clean, then is the target in its range?
- Trap: repeated values, which can make a messy half look clean.