Search In Rotated Sorted Array

Medium · Binary Search

You are given an array of distinct integers that was originally sorted in increasing order but then rotated at some unknown pivot point. Given a target value, return its index in the array, or -1 if it is not present. You must not simply scan the whole array; treat the search as if it should exploit the array's partial ordering.

Examples

Input:  nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Why:    The array was sorted then rotated, and value 0 sits at index 4.

Input:  nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Why:    3 does not appear anywhere in the array.

Input:  nums = [1], target = 0
Output: -1
Why:    The only element is 1, which is not 0, so nothing matches.

Constraints

1 <= nums.length <= 5000, -10^4 <= nums[i] <= 10^4, all values in nums are unique, nums is originally sorted ascending then rotated at some pivot, -10^4 <= target <= 10^4

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Search In Rotated Sorted Array

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Search In Rotated Sorted Array. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.