Search in a Rotated Array

A strictly increasing array was rotated: some number of its first elements were moved, in order, to the end. [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. It may also not have been rotated at all.

Given the rotated array nums and a target, return the position of target, or -1 if it isn't there. Aim for O(log n).

Constraints

  • 1 ≤ length of nums ≤ 5,000
  • -10,000 ≤ nums[i], target ≤ 10,000
  • The values in nums are all different.

Example 1

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

0 is at position 4.

Example 2

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

3 is not there.

Example 3

Input
nums = [1]
target = 0
Output
-1
Why:

A single number that isn't the target.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –