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;
    }
    
}
Search in Rotated Sorted Array
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


/**
 * @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;
};
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;
    }
};