class Solution:
    def binarySearch(self, nums, target):
        start, end = 0, len(nums) - 1 

        while start <= end: 
            middle = (start + end) // 2 
            current = nums[middle] 

            if target > current: 
                start = middle + 1 
            elif target < current: 
                end = middle - 1 
            else: 
                return middle
                #return current if you want value instead of index 
        return -1 
    
    
    def search(self, nums: List[int], target: int) -> int:
        if len(nums) == 0: 
            return -1 
        elif len(nums) == 1: 
            if nums[0] != target: 
                return -1 
            else: 
                return 0 
        else: 
            rotated = False
            lastIdx = len(nums) - 1 

            if nums[lastIdx] < nums[0]: 
                rotated = True 

            if rotated == False: 
                return self.binarySearch(nums, target) 
            else: 
                previous = nums[0]
                rotateIdx = 0 
                for i in range(1, len(nums)): 
                    if nums[i] < previous: 
                        rotateIdx = i 
                    previous = nums[i]
                    
                array1 = nums[:rotateIdx]
                array1Length = len(array1)
                array2 = nums[rotateIdx:] 

                if self.binarySearch(array1, target) == -1 and self.binarySearch(array2, target) != -1: 
                    return array1Length + self.binarySearch(array2, target)
                return self.binarySearch(array1, target)