33. Search in Rotated Sorted Array.py

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = start + (end - start) // 2 # mid is a pivot index
            if nums[mid] == target:
                return mid
            elif nums[mid] >= nums[start]:
                if nums[mid] > target and nums[start] <= target:
                    end = mid -1
                else: 
                    start = mid +1
            else: # nums[mid] < nums[start]:
                if nums[mid] < target and nums[end] >= target: 
                    # need to includes start or end , corner case
                    start = mid +1
                else:
                    end = mid -1 
        return -1