Rotated Sorted Arrays

A rotated sorted array, such as [4, 5, 6, 7, 0, 1, 2], is a sorted array cut at some point and swapped around. It isn't sorted overall, but binary search still works. Split it at mid, and at least one half is always sorted. Find that half, decide whether the target can be in it, and drop the other side.

The idea#

The first job each step is to find the sorted half. Compare nums[mid] with nums[r]:

If nums[mid] < nums[r], the right half mid..r is increasing (the rotation point isn't in it).
Otherwise, the left half l..mid is increasing.

Once you know which half is sorted, you know its range from its two ends. If the target lies between its ends, search there; if not, it must be in the other half. Every step still halves the range, so the search is $O(\log n)$ .

Some problems ask for the minimum instead of a target, and that's a different question. It's a tipping-point problem: the same mid versus r comparison tells you which side of mid holds the drop. See Tipping Point & Peak.

How to spot it#

These cues point to the rotated-array pattern.

"Rotated sorted array", "rotated at an unknown pivot".
Find the minimum, the rotation count, or a target in such an array.
You need $O(\log n)$ on an array that is sorted except for one drop.

Template#

Search for a target. Each branch first finds the sorted half, then checks whether the target is inside it.

l, r = 0, len(nums) - 1
while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target: return mid
    if right half mid..r is sorted:        # nums[mid] < nums[r]
        if target is inside its range: go right
        else: go left
    else:                                  # left half l..mid is sorted
        if target is inside its range: go left
        else: go right
return -1

To see how the sorted half changes from step to step, here is the trace for target 0 in [4, 5, 6, 7, 0, 1, 2].

`l`	`r`	`mid`	Sorted half	Target 0 inside?	Move
0	6	3 (7)	left `[4..7]`	✗	`l = 4`
4	6	5 (1)	right `[1..2]`	✗	`r = 4`
4	4	4 (0)		found	return 4

Pitfalls#

The loop shape is standard, so most bugs hide in the comparisons.

Comparing with the wrong end. Comparing mid with r keeps the cases clean. When comparing with l, the "no rotation" case needs extra care.
Strict vs inclusive checks. nums[mid] was already tested, so use nums[mid] < target <= nums[r] and nums[l] <= target < nums[mid].
Expecting $O(\log n)$ with duplicates. A tie between mid and an end tells you nothing, so the worst case can be $O(n)$ . Say so in an interview.
Dropping a possible answer. When mid itself may be the answer, keep it in the range (r = mid with l < r).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Search in Rotated Sorted Array

This is the template. Use the strict and inclusive checks from the pitfalls so nums[mid] is never counted twice.

Hint: Search in Rotated Sorted Array II

With duplicates, nums[mid] == nums[r] tells you nothing: either half could hold the drop (think [1, 1, 1, 3, 1]). The safe move is r -= 1. It removes one copy of a value still present at mid, so nothing is lost, but the worst case becomes $O(n)$ .

Hint: Find Minimum in Rotated Sorted Array

Use l < r. If nums[mid] < nums[r], the minimum is at mid or to its left, so set r = mid. Otherwise the drop is right of mid, so set l = mid + 1. Don't use r = mid - 1: mid may be the minimum.

Hint: Find Minimum in Rotated Sorted Array II

Use the same loop, plus the duplicate rule: if nums[mid] == nums[r], do r -= 1. The worst case is again $O(n)$ .

Key takeaways#

Split at mid and one half is always sorted.
Compare nums[mid] with nums[r] to tell which half that is.
Search the sorted half if the target fits its range; otherwise go to the other half.
Finding the minimum is a tipping point: r = mid or l = mid + 1.
Duplicates force r -= 1 on ties, making the worst case $O(n)$ .

Core idea#

A rotated sorted array is a sorted array cut at one point and swapped around. Split it at mid and at least one half is always sorted. Find that half, check whether the target fits its range, and drop the other side.

Key points#

Compare nums[mid] with nums[r].
If nums[mid] < nums[r], the right half mid..r is sorted. Otherwise the left half l..mid is sorted.
If the target lies between the ends of the sorted half, search there. If not, search the other half.
Each step halves the range, so the search is $O(\log n)$ .
Finding the minimum is a tipping point. If nums[mid] < nums[r], set r = mid. Otherwise set l = mid + 1. Use l < r.
Duplicates: nums[mid] == nums[r] tells you nothing. Do r -= 1. The worst case becomes $O(n)$ .
Spot it: "rotated sorted array", "unknown pivot", find the minimum, the rotation count or a target.

Template#

l, r = 0, len(nums) - 1
while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target: return mid
    if nums[mid] < nums[r]:                # right half sorted
        if nums[mid] < target <= nums[r]: l = mid + 1
        else: r = mid - 1
    else:                                  # left half sorted
        if nums[l] <= target < nums[mid]: r = mid - 1
        else: l = mid + 1
return -1

Pitfalls#

Comparing with the wrong end. Compare mid with r for clean cases. Comparing with l makes the no-rotation case harder.
Strict vs inclusive checks. nums[mid] is already tested, so use nums[mid] < target <= nums[r] and nums[l] <= target < nums[mid].
r = mid - 1 when you find the minimum. mid may be the minimum, so use r = mid.
Promising $O(\log n)$ with duplicates. Say that the worst case is $O(n)$ .

Say it in an interview#

"One half is always sorted. Check if the target fits that half's range."
"With duplicates, a tie at mid and r forces r -= 1, so the worst case is O(n)."