Search in a Rotated Sorted Array

MediumArraysBinary search243 tests

An array nums of distinct integers was first sorted in ascending order. Then it was rotated: some number of values were moved from the front to the back, keeping their order. The number of moved values can be zero.

You also get an integer target. Return the index of target in nums, or -1 if it is not in the array.

Your solution should run in O(log n) time.

Hint: when you cut the array in the middle, at least one of the two halves is sorted. Check the first and last value of that half to decide if target can be inside it.

Examples

Example 1

Input:: [15,18,22,3,6,9,11], 6
Output:: 4

The array is 3, 6, 9, 11, 15, 18, 22 rotated so that it starts at 15. The value 6 is at index 4.

Example 2

Input:: [15,18,22,3,6,9,11], 20
Output:: -1

20 is not in the array, so the answer is -1.

Example 3

Input:: [5,8,13], 13
Output:: 2

This array was rotated by zero, so it is just sorted. 13 is at index 2.

Constraints

1 <= nums.length <= 40
-1000 <= nums[i], target <= 1000
All values in nums are different.
nums is an ascending array rotated by some amount (possibly zero).

Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.