noodleProblems/
Search in Rotated Sorted Array
#42

Search in Rotated Sorted Array

AlgorithmmediumArrayBinary Search

An ascending array of **distinct** integers nums was rotated at some unknown pivot, so that [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

Given the rotated array and an integer target, return the index of target, or -1 if it is not present. Your algorithm must run in O(log n) time.

Example cases

  • found in tail
    in nums = [4,5,6,7,0,1,2], target = 0
    out 4
    0 sits at index 4 in the rotated array.
  • absent
    in nums = [4,5,6,7,0,1,2], target = 3
    out -1
  • single element
    in nums = [1], target = 0
    out -1

Constraints

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array rotated at some pivot.
  • -10^4 <= target <= 10^4
Saved
nums =
[4,5,6,7,0,1,2]
target =
0