Search in Rotated Sorted ArrayMedium

Search in Rotated Sorted Array

Medium 26.3k40% acceptance

ArrayBinary Search

An ascending array of distinct integers nums was rotated at some unknown pivot. Given nums and a target, return the index of target if it is present, otherwise return -1.

Your algorithm must run in O(log n) time.

Example 1

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

The value 0 sits at index 4.

Example 2

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: -1

3 is not in the array.

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
All values are distinct and nums was originally ascending.

Asked atAmazonMetaMicrosoftGoogle

JavaScript

⌘↵ to run

Loading editor…

Case 1

[4,5,6,7,0,1,2], 0

expected: 4

Case 2

[4,5,6,7,0,1,2], 3

expected: -1

Case 3

[1], 0

expected: -1

Case 4

[5,1,3], 5

expected: 0

Case 5

[4,5,6,7,8,1,2,3], 8

expected: 4

Case 6

[6,7,8,1,2,3,4,5], 3

expected: 5