Search in Rotated Sorted Array

Q: What is the time complexity of searching a rotated sorted array?

O(log n) time and O(1) extra space. Each step keeps one half of the range, so 5000 elements need at most 13 steps. Finding the rotation point first is also O(log n) , with about twice as many steps.

Q: Does the algorithm work when the array contains duplicates?

Not as written. When nums[lo] , nums[mid] and nums[hi] are equal, neither half can be proven sorted. The usual fix moves lo forward by one in that case, which keeps the answer correct but makes the worst case O(n) .

Q: Should you find the rotation point first or search in one pass?

Both run in O(log n) . Finding the minimum first splits the problem into two plain binary searches. The one-pass search does the job in a single loop with fewer steps, and it is the version most interviewers expect.

MediumBinary search

+10

A list of distinct integers was sorted in increasing order and then rotated: some number of elements, possibly zero, were taken from the front and moved to the back in the same order. For example, [2, 5, 8, 11, 15, 19, 23] rotated by 4 becomes [15, 19, 23, 2, 5, 8, 11]. You get the rotated list nums and an integer target. Return the index of target in nums, counting from 0, or -1 if it is not there, in O(log n) time.

Function

search(nums: integer-array, target: integer) → integer

numsinteger-array: the rotated sorted list of distinct integers
targetinteger: the value to look for
Returnsinteger: the index of target in nums, or -1 if it is missing

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i], target ≤ 10⁴
All values in nums are distinct.
nums is an increasing list rotated by some k with 0 ≤ k < nums.length; k = 0 leaves it unrotated.

Examples

Input: nums = [15, 19, 23, 2, 5, 8, 11]target = 5
Output: 4
Explanation: The first middle, index 3, holds 2, so the right half [2, 5, 8, 11] is sorted and holds 5. The next middle, index 5, holds 8; the sorted left part [5, 8] holds 5, which leads to index 4.

Input: nums = [40, 50, 60, 70, 10, 20, 30]target = 65
Output: -1
Explanation: 65 would belong between 60 and 70, and no element holds it. The first middle, 70, puts 65 inside the sorted left part [40, 50, 60, 70], and the range shrinks there until it is empty.

Input: nums = [8, 13, 21, 1, 3, 5]target = 13
Output: 1
Explanation: The first middle, index 2, holds 21. The left part [8, 13, 21] is sorted and 13 lies between 8 and 21, so the right part is dropped. The search then finds 13 at index 1.

Follow-up

If nums may contain duplicates, no algorithm can promise O(log n). Can you prove it with a rotated list of 1s that hides a single 0?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A rotated sorted list is two sorted runs: [15, 19, 23] and then [2, 5, 8, 11]. Comparing target with the middle value no longer tells you which side holds it. But wherever you cut the list, at least one half is sorted, and one comparison tells you whether target can be in that half.

Scan every element

Intuition

Check every index and return the first whose value equals target, or -1 after the loop. It reads every element, so it is correct for any list. It ignores the two sorted runs: 5000 elements cost up to 5000 comparisons, where a binary search needs 13.

Algorithm

For each index i from 0 to n-1, compare nums[i] with target.
If they are equal, return i.
After the loop, return -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Find the rotation point, then binary search

Intuition

The second run starts at the smallest value; call its index k. Both nums[k..n-1] and nums[0..k-1] are sorted, and every value in the first run is larger than every value in the second. Once you know k, comparing target with nums[k] and nums[n-1] picks the run, and plain binary search finishes.

To find k, compare the middle value with nums[hi]. If nums[mid] > nums[hi], the values drop somewhere after mid, so the minimum is to its right. Otherwise nums[mid..hi] climbs with no drop, so the minimum is at mid or before it. In the first example the middles are 2, 19 and 23, giving k = 3, and 5 lies between nums[3] = 2 and nums[6] = 11. Two binary searches cost about 2 log2 n steps.

Algorithm

Set lo = 0 and hi = n-1. While lo < hi, compute mid; if nums[mid] > nums[hi] set lo = mid + 1, otherwise set hi = mid.
The final index k holds the smallest value.
If nums[k] ≤ target ≤ nums[n-1], binary search indexes k to n-1; otherwise search 0 to k-1.
Return the index found, or -1 if the range empties.

def search(nums, target):
    n = len(nums)
    # 1. Find k, the index of the smallest value, where the second run starts.
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the drop is right of mid
        else:
            hi = mid      # mid is in the low run: the minimum is at mid or left of it
    k = lo
    # 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
    if nums[k] <= target <= nums[n - 1]:
        lo, hi = k, n - 1
    else:
        lo, hi = 0, k - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

One binary search on the sorted half

Intuition

Keep the promise of binary search: if target is in the list, its index lies between lo and hi. The values drop only once in the whole list, so at most one of the two halves around mid holds the drop, and the other is sorted. If nums[lo] ≤ nums[mid], the left half is sorted; otherwise the right half is.

For the sorted half, a range test on its two ends says whether target can be inside, for example nums[lo] ≤ target < nums[mid] on the left. If it can, search there; if not, target can only be in the other half. Each step halves the range: at most 13 steps for 5000 elements.

Algorithm

Set lo = 0 and hi = n-1.
While lo ≤ hi, compute mid and return it if nums[mid] equals target.
If nums[lo] ≤ nums[mid], the left half is sorted: set hi = mid - 1 when nums[lo] ≤ target < nums[mid], otherwise lo = mid + 1.
Otherwise the right half is sorted: set lo = mid + 1 when nums[mid] < target ≤ nums[hi], otherwise hi = mid - 1.
When the loop ends, return -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:
            # nums[lo..mid] is sorted: target is in it only if it fits its range
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # nums[mid..hi] is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Pitfalls and edge cases

Writing nums[lo] < nums[mid] instead of ≤. With two elements left, mid equals lo, and the strict test calls [9, 4] a sorted right half: target = 4 returns -1.
Comparing target with nums[mid] first. In the first example with target = 19, the middle 2 is smaller, so the search moves right and misses index 1.
Testing only one end of the sorted half. In [40, 50, 60, 70, 80, 10, 20] with target = 80, target ≥ nums[lo] alone sends the search into [40, 50, 60, 70].
In Rust, k - 1 on a usize underflows when k = 0, the unrotated list. Use half-open ranges.
In Lua and R, returning the 1-based position. Subtract 1.

Frequently asked questions3

What is the time complexity of searching a rotated sorted array?

O(log n) time and O(1) extra space. Each step keeps one half of the range, so 5000 elements need at most 13 steps. Finding the rotation point first is also O(log n), with about twice as many steps.

Does the algorithm work when the array contains duplicates?

Not as written. When nums[lo], nums[mid] and nums[hi] are equal, neither half can be proven sorted. The usual fix moves lo forward by one in that case, which keeps the answer correct but makes the worst case O(n).

Should you find the rotation point first or search in one pass?

Both run in O(log n). Finding the minimum first splits the problem into two plain binary searches. The one-pass search does the job in a single loop with fewer steps, and it is the version most interviewers expect.

def search(nums, target):
    # Write code here

Test #1

Test #2

Test #3

Arguments

nums = [15, 19, 23, 2, 5, 8, 11]
target = 5

Expected Output

Search in Rotated Sorted Array

Function

Constraints

Examples

Hints

Solution

Scan every element

Find the rotation point, then binary search

One binary search on the sorted half

Pitfalls and edge cases

Frequently asked questions3

Similar problems