Search in Rotated Sorted Array II

Patrick Leaton
Published: July 5, 2021, 12:29 a.m.
Problem Description

You are given an integer array nums sorted in ascending order (not necessarily distinct values), and an integer target.

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

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

 

Example 1:

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

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

 

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

 

Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates. Would this affect the run-time complexity? How and why?

 

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

Problem Solution

#O(Log(N)) Average, O(N) Worst 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 True
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            elif nums[mid] > nums[right]:
                if  nums[left] <= target and target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if  nums[mid] < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

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.

The only difference between this variation of the problem and the previous is the introduction of possible duplicate values.  These won't pose a threat unless we get to a point where both our left, middle, and right pointers are on a duplicate value.  If this is the case, we will move the left and right pointers inward to continue our search.

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 True

 

If all three pointers share the same value, we are gridlocked.

To continue, we will move the left and right pointers inward and reduce the bounds of our search by two indices.

            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1

 

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]

            elif 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, we can see in the test case shown below that four, the left pointer is not less than or equal to zero, the target. 

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

 

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. 

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

 

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

        return False