There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 &lt;= k &lt; nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

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

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 5000
	-104 &lt;= nums[i] &lt;= 104
	All values of nums are unique.
	nums is an ascending array that is possibly rotated.
	-104 &lt;= target &lt;= 104


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        
        while l<=r:
            mid = (l+r)//2
            if target == nums[mid]:
                return mid
            
            if nums[l]<=nums[mid]:
                if target > nums[mid] or target<nums[l]:
                    l = mid + 1
                else:
                    r = mid - 1
            
            else:
                if target < nums[mid] or target > nums[r]:
                    r = mid - 1
                else:
                    l = mid + 1
        
        return -1
class Solution {
    public int search(int[] nums, int target) {
        int pivot = findPivot(nums);
        int ans = binarySearch(nums, target, 0, pivot);
        if(ans!=-1){
            return ans;
        }
        return binarySearch(nums, target, pivot+1, nums.length-1);
    }
    
    public int findPivot(int[] arr){
        int start = 0, end = arr.length-1;
        while(start<=end){
            int mid = start + (end-start)/2;
            if(mid<end && arr[mid]>arr[mid+1]){
                return mid;
            }
            if(mid>start && arr[mid-1]>arr[mid]){
                return mid-1;
            }
            if(arr[mid]<=arr[start]){
                end = mid-1;
            }else{
                start = mid+1;
            }
        }
        return -1;
    }
    
    public int binarySearch(int[] arr, int target, int start, int end){
        
        while(start<=end){
            int mid = start+ (end-start)/2;
            
            
                if(target<arr[mid]){
                    end = mid-1;
                }else if(target>arr[mid]){
                    start = mid+1;
                }else{
                    return mid;
                }
            
            
        }
        return -1;
    }
    
}
class Solution 
{
public:
    int search(vector<int>& nums, int target) 
    {
        int n=nums.size()-1;
        if(nums[0]==target)
            return 0;
        if(nums.size()==1)
           return -1; 
        // find the index of the minimum element ie pivot
        int pivot=-1;
        int low=0;
        int high=n;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(mid==0)
            {
                if(nums[mid]< nums[mid+1] && nums[mid]< nums[n])
                {
                    pivot=mid;
                    break;
                }
                else
                {
                    low=mid+1;
                }
            }
            
            else if(mid==n)
            {
                if(nums[mid] < nums[0] && nums[mid] < nums[mid-1])
                {
                    pivot=mid;
                    break;
                }
                else 
                {
                    high=mid-1;
                }
            }
            else if(nums[mid]<nums[mid+1] && nums[mid]<nums[mid-1])
            {
                pivot=mid;
                break;
            }
            else if(nums[mid]>=nums[0] && nums[mid]<=nums[n])
                high=mid-1;
            else if(nums[mid] >= nums[0])
                low=mid+1;
            else if(nums[mid] < nums[0])
                high=mid-1;
        }
        cout<<pivot<<endl;
        if(target < nums[0])
        {
            int low1=pivot;
            int high1=n;
            while(low1<=high1)
            {
                int mid1=(low1+high1)/2;
                if(nums[mid1]==target)
                    return mid1;
                else if(nums[mid1] > target)
                    high1=mid1-1;
                else if(nums[mid1]<target)
                    low1=mid1+1;
            }
            
        }
        if(target > nums[0])
        {
            int low2=0;
            int high2=pivot-1;
            if(pivot==0)
            {
                low2=0;
                high2=n;
            }
            while(low2<=high2)
            {
                int mid2=(low2+high2)/2;
                if(nums[mid2]==target)
                    return mid2;
                else if(nums[mid2] > target)
                    high2=mid2-1;
                else if(nums[mid2]<target)
                    low2=mid2+1;
            }
        }
        return -1;
    }
};
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    const len = nums.length;
    if (len === 1 && nums[0] === target) return 0;
    const h = nums.findIndex((val, i) => nums[i === 0 ? nums.length - 1 : i - 1] > val);
    if (h !== 0) nums = nums.slice(h).concat(nums.slice(0, h));
    // console.log(h, nums)
    let lo = 0, hi = len - 1;
    while (lo !== hi) {
        if (lo + 1 === hi) {
            if (nums[lo] === target) return (lo + h) % len;
            if (nums[hi] === target) return (hi + h) % len;
            break;
        }

        const i = Math.floor((lo + hi + 1) / 2);
        // console.log(lo, hi, i)
        const val = nums[i];
        if (val === target) return (i + h) % len;
        if (val > target) hi = i;
        else lo = i;
    }

    return -1;
};
Search in Rotated Sorted Array