Search in Rotated Sorted Array – Python 3 ( Week 11 – 04)

   class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = int(start + (end - start) / 2)

            if nums[mid] >= nums[start]:
                if nums[start] <= target <= nums[mid]:
                    end = mid
                else:
                    start = mid            
            else:
                if  nums[mid] <= target <= nums[end]:
                    start = mid
                else:
                    end = mid
                    
        if nums[start] == target:
            return start
        elif nums[end] == target:
            return end
        
        return - 1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        min_index = self.find_min_index(nums)
        
        if target <= nums[-1]:
            return self.find_target_index(nums[min_index:], target, min_index)
        else:
            return self.find_target_index(nums[:min_index], target, 0)
        
        
    def find_min_index(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[start] > nums[end] and nums[start] < nums[mid]:
                    start = mid
            else:
                    end = mid
        
        if nums[start] < nums[end]:
            return start
        else:
            return end
    
    def find_target_index(self, nums, target, index) -> int:
        if not nums:
            return -1
        
        start = start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] > target:
                end = mid
            else:
                start = mid
            
        if nums[start] == target:
            print(start)
            return index + start
        elif nums[end] == target:
            return index + end
        else:
            return -1