33. Search in Rotated Sorted Array

1^o 若target在A与D之间，要么位于AB之间，要么位于CD之间，那么当target在A-min1或者mid2-D之间是确定的二分查找，当在mid1-mid2之间就是和原来问题相同的子问题，递推即可，找得到下标就证明存在，找到最后都没找到，就证明不存在。
2^o 若target不在A与D之间，那肯定就在AD之间时找不到。

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

进阶：Search in Rotated Sorted Array II