Search in Rotated Sorted Array with Duplicates

Prerequisites: 🎞️Check if an array is sorted and rotated, ⁉️Thought Experiment, Does an array need to be sorted to run Binary Search? 📉The Minimum in a Rotated Sorted Array, Minimum in Rotated Sorted Array with Duplicates

Question

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

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

Implementation 1.0

1. This question simply builds on 🔎Search in Rotated Sorted Array. and Minimum in Rotated Sorted Array with Duplicates
2. We simply find the minimum, giving us two sorted halves, and run a Binary search on each half. If the value is found in either half we simply return
1. The solution to this has been implemented in 🔎Search in Rotated Sorted Array, the only difference is to find the minimum we will use our solution from Minimum in Rotated Sorted Array with Duplicates as that gives us the accurate minimum.

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition

The Theoretical time complexity is O log(n) but we are running a logarithmic search twice.

1. Finding the minimum O log(n)
2. Binary Search on the upper half of the array and the lower half. O log(n)

Can there be a way where we can do it by running a logarithmic search only once?

Implementation 2.0

1. In the previous solution where in the section Reframe the problem 2.0 of 🔎Search in Rotated Sorted Array.
1. We used the sorted-ness of the array to our advantage by splitting it into two halves, the upper and lower half.
1. Then we check which half the target and the mid are in.
1. If they are the same, we can reduce the problem to a simple 🍦Binary Search(Vanilla) problem.
2. If they are not, we can move toward the array which contains the target element.
2. How does having duplicate change our plans?
1. Previously, we used the last element to determine which half of the array we were in, but duplicates can cause confusion for our algorithm. This can lead to problems when we have circular duplicates (duplicates that appear in both halves of the array), similar to the one described in Minimum in Rotated Sorted Array with Duplicates (refer to 4.b).

Copy

targetInUpperHalf = target > nums[-1]
targetInLowerHalf = target <= nums[-1] 

midInUpperHalf = nums[mid] > nums[-1]
midInLowerHalf = nums[mid] <= nums[-1]


‣
Dry run example of why this will not work
3. In the question Minimum in Rotated Sorted Array with Duplicates . We get rid of these circular duplicates by removing elements from the right side until we had a normalized array (no same duplicates in both halves)
1. Step 1 circularDuplicates = nums[mid] == nums[right] is True

2. Step 2 remove the right pointer(hypothetical last Element) by one to the left.

3. This will leave us with a normalized array and give us a new hypothetical last element which will be in the place of the rightmost element. Changes to the code from 🔎Search in Rotated Sorted Array
Copy

targetInUpperHalf = target > nums[right]
targetInLowerHalf = target <= nums[right] 

midInUpperHalf = nums[mid] > nums[right]
midInLowerHalf = nums[mid] <= nums[right]

4. Will the duplicates in separate halves matter (3s in the upper half in the image below)

1. No, as they will not confuse us as to which half the target and mid are and they will be taken care of by regular binary search. You can test arrays on the previous solution 🔎Search in Rotated Sorted Array to see for yourself.
1. With circular duplicates [3, 3, 3, 3, 4, 0, 1, 3], without circular duplicates [3, 3, 3, 3, 3, 3, 4, 0, 1].
5. When we get a circular duplicate we move the right pointer one element to the right. And go to the next iteration of the loop.
Copy

circularDuplicates = nums[mid] == nums[right]
  
if circularDuplicates:
    right -= 1
        
# Regular Binary Search
elif (midInUpperHalf == targetInUpperHalf) or (midInLowerHalf == targetInLowerHalf):
    if target > nums[mid]:
        left = mid + 1   
    else:
        right = mid - 1

else: # target and mid are not in the same half
    if targetInUpperHalf: # mid is the lower
        right = mid - 1
    else: # targetInLowerHalf mid in upper half
        left = mid + 1

6. Two if statements vs elif? Why
Copy

     if target == nums[mid]:
         return True

	   elif circularDuplicates:
	       right -= 1
	            

1. [2,2,2,2,2,2,2,2,2] target = 2. This will get rid of all the duplicates before returning the target.

‣
We can also use a while loop to remove duplicates before beginning a regular binary search. However, this requires additional bookkeeping(around circular duplicates and midpoint), so it is better to use an if statement instead.“
4. Will this deal with multiple duplicates in the lower half that might still confuse the algorithm? Yes. As talked about already in Minimum in Rotated Sorted Array with Duplicates

1. We are removing the duplicates from the right side one by one from the upper half, in a case like this the midpoint will only move to the left. Since the array is circular, the elements on the left of the midpoint (in the upper half) will still be duplicates. The right and mid-pointers move in a circular manner until all the duplicates are eliminated.
Copy

[3,1,2,3,3,3,3,3,3,3]
           ^       ^
           M    <--R

[3,1,2,3,3,3,3,3,3,X]
         ^       ^
         M    <--R

[3,1,2,3,X,X,X,X,X,X] # all duplicates removed in the upper half
 ^     ^
 M  <--R

[3,1,2,3,X,X,X,X,X,X] # Now duplicates will be removed from the lower half
 ^     ^
 M  <--R

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
    
        
        left,right = 0, len(nums)-1
        
        while left <= right:
            
            mid = left + (right - left) //2
        
            #duplicates
            
            circularDuplicates = nums[mid] == nums[right]
            
            targetInUpperHalf = target > nums[right]
            targetInLowerHalf = target <= nums[right] 
            
            midInUpperHalf = nums[mid] > nums[right]
            midInLowerHalf = nums[mid] <= nums[right]

            
					
            if target == nums[mid]:
                return True

            elif circularDuplicates:
                right -= 1
                    
                    
            # Regular Binary Search
            elif (midInUpperHalf == targetInUpperHalf) or (midInLowerHalf == targetInLowerHalf):
                if target > nums[mid]:
                    left = mid + 1   
                else:
                    right = mid - 1
            
            else: # target and mid are not in the same half
                if targetInUpperHalf: # mid is the lower
                    right = mid - 1
                else: # targetInLowerHalf mid in upper half
                    left = mid + 1 

        return False

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(n)

Space Complexity: O(1)

This will not be a logarithmic time in the worst case[2,1,1,1,1,1,1,1,1,1,1,1,1,1] for a case like this we will start from the right and keep going to the right so we will have to go over almost every element so that will move our complexity to O(n).