Search in Rotated Array

Find the index of a target in a rotated sorted array in O(log n) time.

binary-search arrays search rotated-sorted

You are given a list of integers `nums` that was originally sorted in ascending order but then rotated at some unknown pivot (e.g., `[0,1,2,4,5,6,7]` might become `[4,5,6,7,0,1,2]`). You are also given an integer `target`. Write a function `search_rotated(nums, target)` that returns the index of `target` in `nums`, or `-1` if it is not present. Your solution must run in O(log n) time. The list may contain duplicate values.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
The function should run in O(log n) time on average.

Example

>>> search_rotated([4,5,6,7,0,1,2], 0)
4
>>> search_rotated([4,5,6,7,0,1,2], 3)
-1
>>> search_rotated([1], 0)
-1

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Remember that at least one half of the array is always sorted in a rotated sorted array.

When comparing the middle element, decide whether the left half is sorted by checking if nums[low] <= nums[mid].

If duplicates exist, when left, middle, and right values are equal, you may need to shrink the search range by one.

The standard binary search logic can be adapted by checking which side is sorted and then determining if the target lies in that side.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.