Search in Rotated Sorted Array

Take a sorted list, cut it at some point, and swap the two pieces: [0, 1, 2, 4, 5, 6, 7] becomes [4, 5, 6, 7, 0, 1, 2]. It is no longer sorted, so the plain template gives wrong answers. But it is almost sorted — two sorted runs, one after the other — and that is enough to keep O(log n).

This is one of the most asked binary search problems at large companies. It tests whether you understand why binary search works, because the fix is not a new template. It is one extra question at each step.

The problem

A list of distinct integers was sorted in increasing order and then rotated at an unknown index, so its tail moved to the front. Given the rotated list and a target, return the target's index, or -1 if it is absent. The solution must run in O(log n).

• nums = [4, 5, 6, 7, 0, 1, 2], target = 0 → 4.
• Same nums, target = 3 → -1.

Constraints: 1 ≤ len(nums) ≤ 5000, values distinct, between -10⁴ and 10⁴. The rotation may be zero, so the list may be plainly sorted.

Clarifying questions

• Are the values distinct? Yes. (With duplicates the problem changes; see the follow-ups.)
• Could the list not be rotated at all? Yes, and the solution must still work.
• Do I know the rotation point? No. Finding it is part of the problem.
• Index or value? The index in the rotated list.

Approach 1: the simple way

Scan every element.

1def search_rotated_linear(nums: list[int], target: int) -> int:2    """Scan every element: O(n)."""3    for i, value in enumerate(nums):4        if value == target:5            return i6    return -1

Time: O(n). Space: O(1).

It is correct, and for 5,000 values it is fast. But it throws away the fact that the list is two sorted runs, and the problem explicitly asks for O(log n): about 13 steps here instead of 5,000. An interviewer will not accept the scan as a final answer.

The key insight

A rotated sorted list has exactly one drop: one place where a value is followed by a smaller one. In [4, 5, 6, 7, 0, 1, 2] the drop is between 7 and 0. Everywhere else, values go up.

Now cut any range [left, right] at mid. The drop can be in the left half or in the right half, but not in both, because there is only one. So at least one half has no drop, and that half is sorted. You can tell which with a single comparison:

• If nums[left] <= nums[mid], the values climb from left to mid without falling, so the left half is sorted.
• Otherwise the drop is between left and mid, so the right half is sorted.

A sorted half is useful because you can test in O(1) whether the target lies inside it: it does exactly when the target is between the half's two end values. If the target is inside the sorted half, search there. If not, it can only be in the other half — the messy one — so search there. Either way, half the range is gone, and the other half is again a rotated sorted list (or a plain sorted one), so the same step works again.

Take the first step on the example: left = 0, right = 6, mid = 3. nums[0] = 4 is at most nums[3] = 7, so [4, 5, 6, 7] is sorted. The target 0 is not between 4 and 7, so it must be on the right. Indices 0 to 3 are gone after one comparison, even though the list is not sorted.

Approach 2: one pass, two questions per step

1def search_rotated(nums: list[int], target: int) -> int:2    """Index of target in a rotated sorted array of distinct values, or -1."""3    left, right = 0, len(nums) - 14    while left <= right:5        mid = left + (right - left) // 26        if nums[mid] == target:7            return mid8        if nums[left] <= nums[mid]:                      # left half [left..mid] is sorted9            if nums[left] <= target < nums[mid]:10                right = mid - 1                          # target is inside the sorted half11            else:12                left = mid + 113        else:                                            # right half [mid..right] is sorted14            if nums[mid] < target <= nums[right]:15                left = mid + 1                           # target is inside the sorted half16            else:17                right = mid - 118    return -1

Step by step: check mid; decide which half is sorted; check whether the target lies inside that half, using the half's end values; move into the half that can hold it. The strict < next to nums[mid] in both range checks is there because nums[mid] has already been ruled out.

Dry run on [4, 5, 6, 7, 0, 1, 2], target 0:

In step 2 the range is [0, 1, 2], which is not rotated at all. The same test handles it: nums[4] = 0 is at most nums[5] = 1, so the left half is sorted.

For target 3, the steps go mid = 3 (not in [4, 7), go right), mid = 5 (not in [0, 1), go right), mid = 6 (value 2, not in [2, 2), go right), and the range empties: -1.

Time: O(log n) — every step halves the range. Space: O(1).

Approach 3: find the rotation point, then search normally

A different plan, which some people find easier to get right: first find the index of the smallest value (the rotation point), which splits the list into two sorted runs. Then decide which run can hold the target and run the plain template on it.

1def find_min_index(nums: list[int]) -> int:2    """Index of the smallest value in a rotated sorted array (distinct values)."""3    left, right = 0, len(nums) - 14    while left < right:5        mid = left + (right - left) // 26        if nums[mid] > nums[right]:7            left = mid + 18        else:9            right = mid10    return left111213def search_rotated_two_step(nums: list[int], target: int) -> int:14    """Find the rotation point, then run a plain binary search on one sorted side."""15    if not nums:16        return -117    pivot = find_min_index(nums)                         # index of the smallest value18    if nums[pivot] <= target <= nums[-1]:19        left, right = pivot, len(nums) - 1               # target can only be in the right run20    else:21        left, right = 0, pivot - 1                       # otherwise only in the left run22    while left <= right:23        mid = left + (right - left) // 224        if nums[mid] == target:25            return mid26        if nums[mid] < target:27            left = mid + 128        else:29            right = mid - 130    return -1

find_min_index is the whole of the next lesson, so it is not explained here. On the example it returns 4 (the 0). The target 0 is between nums[4] = 0 and nums[-1] = 2, so the search runs on indices 4 to 6.

It is two binary searches, so O(log n) time and O(1) space, the same as Approach 2. It is longer, but each piece is a template you already trust. If the one-pass logic starts to tangle during an interview, switching to this is a sound move. All three versions were checked against each other on 400 random rotated lists.

Edge cases

• Not rotated: nums[left] <= nums[mid] is always true, so the code behaves exactly like the plain template.
• Two elements, like [3, 1]: here mid == left, so nums[left] <= nums[mid] compares a value with itself. The <= makes it true, which correctly says "the one-element left half is sorted". See the common mistake below.
• One element: found or not in one step.
• Target equal to an end of the sorted half: the range checks use <= on the far end (nums[left] or nums[right]) so that those values are included.
• Rotation at the last index, like [2, 3, 4, 5, 1]: the right half is the messy one on the first step; the logic does not care where the drop is.

Follow-ups

• "Values can repeat." (Search in Rotated Sorted Array II, return true or false.) When nums[left] == nums[mid] == nums[right], you cannot tell which half is sorted — [3, 1, 3, 3, 3] and [3, 3, 3, 1, 3] look the same at those three points. Shrink both ends by one (left += 1, right -= 1) and continue. The worst case becomes O(n), and that cannot be avoided: an array of all 3s with a single 1 hidden somewhere forces you to look at every element.
• "How many times was it rotated?" The index of the smallest value: find_min_index.
• "Find the smallest value." That is the next lesson.