search_in_rotated_sorted_array 

 1# @leet start
 2class Solution:
 3    def search(self, nums: list[int], target: int) -> int:
 4        """
 5        To search in a rotated sorted array in $O(log n)$ time, we have to do
 6        a modified binary search.
 7
 8        We have three points, the left, mid, and right.
 9        If the array is sorted from left to mid, we can treat it as a normal
10        binary search. However, if it isn't we have to do the modified binary search,
11        where we go in the opposite direction.
12        """
13        l, r = 0, len(nums) - 1
14
15        while l <= r:
16            m = (l + r) // 2
17
18            if nums[m] == target:
19                return m
20            if nums[m] >= nums[l]:
21                if nums[l] <= target < nums[m]:
22                    r = m - 1
23                else:
24                    l = m + 1
25            else:
26                if nums[m] < target <= nums[r]:
27                    l = m + 1
28                else:
29                    r = m - 1
30        return -1
31
32
33# @leet end
34
35
36def test():
37    assert 2 + 2 == 4
class Solution: 
 3class Solution:
 4    def search(self, nums: list[int], target: int) -> int:
 5        """
 6        To search in a rotated sorted array in $O(log n)$ time, we have to do
 7        a modified binary search.
 8
 9        We have three points, the left, mid, and right.
10        If the array is sorted from left to mid, we can treat it as a normal
11        binary search. However, if it isn't we have to do the modified binary search,
12        where we go in the opposite direction.
13        """
14        l, r = 0, len(nums) - 1
15
16        while l <= r:
17            m = (l + r) // 2
18
19            if nums[m] == target:
20                return m
21            if nums[m] >= nums[l]:
22                if nums[l] <= target < nums[m]:
23                    r = m - 1
24                else:
25                    l = m + 1
26            else:
27                if nums[m] < target <= nums[r]:
28                    l = m + 1
29                else:
30                    r = m - 1
31        return -1
def search(self, nums: list[int], target: int) -> int: 
 4    def search(self, nums: list[int], target: int) -> int:
 5        """
 6        To search in a rotated sorted array in $O(log n)$ time, we have to do
 7        a modified binary search.
 8
 9        We have three points, the left, mid, and right.
10        If the array is sorted from left to mid, we can treat it as a normal
11        binary search. However, if it isn't we have to do the modified binary search,
12        where we go in the opposite direction.
13        """
14        l, r = 0, len(nums) - 1
15
16        while l <= r:
17            m = (l + r) // 2
18
19            if nums[m] == target:
20                return m
21            if nums[m] >= nums[l]:
22                if nums[l] <= target < nums[m]:
23                    r = m - 1
24                else:
25                    l = m + 1
26            else:
27                if nums[m] < target <= nums[r]:
28                    l = m + 1
29                else:
30                    r = m - 1
31        return -1

To search in a rotated sorted array in $O(log n)$ time, we have to do a modified binary search.

We have three points, the left, mid, and right. If the array is sorted from left to mid, we can treat it as a normal binary search. However, if it isn't we have to do the modified binary search, where we go in the opposite direction.

def test(): 
37def test():
38    assert 2 + 2 == 4