< 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.