Search in Rotated Sorted Array

Patrick Leaton
Published: March 20, 2021, 3:49 a.m.
Problem Description

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

If target is found in the array return its index, otherwise, return -1.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is guranteed to be rotated at some pivot.
  • -10^4 <= target <= 10^4

 

The description was taken from https://leetcode.com/problems/search-in-rotated-sorted-array/.

Problem Solution

#O(Log(N)) Time, O(1) Space
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right)//2
            if nums[mid] == target:
                return mid
            if nums[mid] > nums[right]: 
                if  nums[left] <= target and target < nums[mid]: 
                    right = mid - 1
                else: 
                    left = mid + 1
            else: 
                if  target <= nums[right] and nums[mid] < target: 
                    left = mid + 1
                else: 
                    right = mid - 1
        return -1

Problem Explanation

The difference between this problem and Find Minimum in Rotated Sorted Array is in that problem, we knew where the target should be since the minimum is the leftmost element in a sorted array so we just had to utilize our pointers to find the nonrotated partition of the array. 

However, in this problem, we have no idea where the target is.  

To account for this, we will need an extra comparison within our binary search algorithm.   The first comparison will be to determine where the array is rotated by finding which pointer shares a partition with the middle one, this was all we needed to keep doing for the previous problem.  If the middle pointer's value is greater than the right one's, then the left pointer shares a partition with the middle pointer and vice versa.  After finding that, we will need a second comparison to choose which partition to continue our search in by both comparing the middle pointer to the target like we usually do in binary search algorithms, but also by comparing the same-partition pointer with the target as well to see if we should abandon that partition.

Let's start by initializing our left and right pointers to be the first and last indices of the array.

        left, right = 0, len(nums) - 1

 

For our search, we will create a loop that will run while our pointers haven't crossed each other.

        while left <= right:

 

At the beginning of each iteration, we will set the middle pointer to be the mean of the left and right pointers.

            mid = (left + right)//2

 

If the element at the middle index is the value we are looking for, we will return our middle index.

            if nums[mid] == target:
                return mid

 

If not, we will start looking for which pointer shares a partition with the middle one.  

If the middle element is greater than the right element, the left pointer does and we have a test case like this, with the target being zero:

                                  [4,5,6,7,0,1,2]

            if nums[mid] > nums[right]:

 

Now, we will need to choose which partition to continue our search in by comparing the middle pointer to the target and the same-partition pointer to the target as well.  If the left value is less than the target and the target is also less than the middle value, we will continue our search in the left partition.  

That isn't the case for our example.

                if  nums[left] <= target and target < nums[mid]: 
                    right = mid - 1

 

Otherwise, in our case, we would choose to abandon the partition and move right.

                                  [4,5,6,7,0,1,2]

                else:
                    left = mid + 1

 

Similar to last time, we will check the same-partition pointer and middle pointer against the target to choose which partition to continue our search in. 

                if  target <= nums[right] and nums[mid] < target: 
                    left = mid + 1
                else: 
                    right = mid - 1

 

If our left and right pointers have overlapped and we never returned anything, we will return a negative one because the target wasn't in the array.

        return -1