< Back 33. Search in Rotated Sorted Array We're given a list of integers, however, they've been rotated at some unknown pivot index, k. The integers we've been provided were originally sorted. We need to provide an algorithm that finds the target integer in the rotated, sorted array in log(n) time. We use binary search to find the target. To deal with the rotated nature of the list, we add a couple more checks at each step of the binary search to eliminate halves of the array. If the current middle integer in the binary search is greater than the target, we would usually assume that we need to search in the left half. Before we do that, though, we check to see if the right half would actually contain the target. If our current number is greater than the number pointed to by the right pointer, we know that the right half contains a portion of the original array that's been rotated to have lower values. We also check to see if nums[r] is greater than or equal to the target. If so, we select the right half to search. Otherwise, we search the left half. If the current middle integer in the binary search is less than the target, we would usually assume that we need to search in the right half. Before we do that, though, we check to see if the left half would actually contain the target. If our current number is less than the number pointed to by the left pointer, we know that the left half contains a portion of the original array that's been rotated to have higher values. We also check to see if nums[l] is less than or equal to the target. If so, we select the left half to search. Otherwise, we search the right half. The solution is as follows: class Solution: def search(self, nums: List[int], target: int) -> int: l, r = 0, len(nums) - 1 while l <= r: m = (r + l) // 2 if nums[m] == target: return m elif nums[m] > target: if nums[m] > nums[r] and nums[r] >= target: l = m + 1 else: r = m - 1 else: if nums[m] < nums[l] and nums[l] <= target: r = m - 1 else: l = m + 1 return -1 _ Time Complexity: O(log(n)) - Where n is the length of the array. _ Space Complexity: O(1) - Binary search requires constant space.