33. Search in Rotated Sorted Array

 1class Solution:
 2    def search(self, nums: List[int], target: int) -> int:
 3        n = len(nums)
 4
 5        # 1. find pivot (nums[0])
 6        l = 0
 7        r = n - 1
 8
 9        while l < r:
10            m = (l + r) // 2
11            # [4,5,6,7,0,1,2] nums[m] > nums[r]
12            # [5,6,7,0,1,2,4] nums[m] < nums[r]
13            # why compare nums[m] and nums[r], why do we ignore nums[l]?
14            # "nums[r] anchors the “true” end of the sorted array, whereas nums[l] can start anywhere depending on the rotation"
15            # good enough for interviews
16            if nums[m] > nums[r]:
17                l = m + 1
18            else:
19                r = m
20            # print(l, r, nums[l])
21
22        pivot = l
23
24        # 2. bisect from pivot (typical binary search)
25        l = 0
26        r = n - 1
27
28        while l <= r:
29            # [4,5,6,7,0,1,2]
30            #  l     m p   r
31            # the Real `m` should be (m + pivot) % n
32
33            # [4,5,6,7,0,1,2]
34            #  l           r
35            #  R                (3 + 4) % 7 = 0
36
37            # [5,6,7,0,1,2,4]
38            #  l     m     r
39            #        p
40            #              R    (3 + 3) % 7 = 6
41
42            m = (l + r) // 2
43            real = (m + pivot) % n
44
45            # typical binary search
46            if nums[real] == target:
47                return real
48            elif nums[real] < target:
49                l = m + 1
50            else:
51                r = m - 1
52
53        return -1