Zero To DSAZero To DSA
Privacy Policy
Binary SearchKth Largest Element in an Array

Search in Rotated Sorted Array

medium
Time: O(log n)
Space: O(1)

There is an integer array sorted in ascending order (with distinct values) that has been rotated. Given the array and a target, return the index of the target. If not found, return -1.

Constraints

  • 1 <= nums.length <= 5000
  • All values are unique.

Examples

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