1def search(nums, target):2    l = 03    r = len(nums) - 14    while l <= r:5        m = l + (r - l) // 26        if nums[m] == target:7            return m8        elif nums[l] <= nums[m]:         # left half [l..m] sorted9            if nums[l] <= target <= nums[m]:10                r = m - 111            else:12                l = m + 113        else:                            # right half [m..r] sorted14            if nums[m] <= target <= nums[r]:15                l = m + 116            else:17                r = m - 118    return -1