Search Rotated Sorted Array

MediumPython

Problem

Find an element in a rotated sorted array.

Asked in the Technical stage. Implement a function that returns the index of target in a rotated, ascending array of distinct integers, or -1 if the target is absent.

Contract

Input: nums, a non-empty list of distinct integers, and integer target.
Output: The zero-based index of target, or -1.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 returns 4.
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 returns -1.

Constraints

1 <= nums.length <= 500
-10^9 <= nums[i] <= 10^9
All values in nums are distinct
nums is sorted in ascending order and then rotated at most once

Function Signature

def search_rotated(nums, target):

Code

Run your code to see test output here.