1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        l, r = 0, len(nums) - 1
4

5
        while l <= r:
6
            mid = (l + r) // 2
7
            if target == nums[mid]:
8
                return mid
9

10
            if nums[l] <= nums[mid]:
11
                if target > nums[mid] or target < nums[l]:
12
                    l = mid + 1
13
                else:
14
                    r = mid - 1
15

16
            else:
17
                if target < nums[mid] or target > nums[r]:
18
                    r = mid - 1
19
                else:
20
                    l = mid + 1
21

22
        return -1