# python3
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        # 二分 始终和最右边对比，正常情况下右边最大
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left+right)//2
            if nums[mid] == target:
                return mid 
            elif nums[mid] >= nums[right]:  # 左边递增，右边单调性不确定
                if nums[right] >= target:  # 说明目标值在右边区间
                    left = mid + 1
                else:
                    right = mid - 1
            else:  # 左边区间不确定单调性 右边区间递增
                if target > nums[mid] and target <= nums[right]:  # 在右边
                    left = mid + 1
                else:
                    right = mid -1
        return -1