Search in Rotated Sorted Array

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

Question

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

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

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

Reframing the problem

1. This question builds on the concepts of 🎞️Check if an array is sorted and rotated and 📉The Minimum in a Rotated Sorted Array It is important to understand:
1. What is a sorted and rotated array
2. How rotating a sorted array gives us two sorted arrays
3. Where the minimum and maximum occur in a sorted and rotated array
4. How to find the minimum in a rotated sorted array
2. The question is relatively straightforward if you have completed the above steps. Let's move on to intuition.

Intuition

1. In the question 🎞️Check if an array is sorted and rotated, we determined that rotating a sorted array gives us two sorted arrays.

2. The minimum element is always the first one in the unrotated/lower half. That happens to be the border between the two arrays, we can use the same approach as we did to find the minimum in 📉The Minimum in a Rotated Sorted Array, and use it to distinguish between the two halves.
1. If the minimum index is i, consider the following:
1. The upper half : [0, i-1]
2. The lower half : [i, len(nums)-1]
2. Since both arrays are sorted, we can run 🍦Binary Search(Vanilla) on each of them. Return the index of the target if it is found in either array. Else return -1 if not found in either.

Code

1. Find the minimum index in the rotated sorted array. 📉The Minimum in a Rotated Sorted Array + Slight modification; instead of the value we return the index.
Copy

class Solution:
    def findMin(self, nums):

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

        while left <= right:
            
            mid = left + (right - left) // 2


            #True
            InLowerHalf = nums[mid] <= nums[-1]
            if InLowerHalf:
                possibleMin = mid
                right = mid - 1

            #False
            else:
                left = mid + 1
            
        # returning the index instead the value
        return possibleMin # <--change here

2. Binary Search from 🍦Binary Search(Vanilla) + Slight modification
1. Instead of passing a split array into Binary Search, we'll pass the start and end indexes. This way, we can return the indexes from the original array when returning the answer.
Copy

def binarySearch(self,left,right,nums,target):


        while left <= right:

            mid = right + (left-right) //2

            if target == nums[mid]:
                return mid

            elif target > nums[mid]:
                left = mid + 1

            elif target < nums[mid]:
                right = mid - 1

        # not found :(
        return -1

3. FInd minimum + Binary search
Copy

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        minIndex = self.findMin(nums)

	  
        targetInUpperHalf = self.binarySearch(0,minIndex-1,nums,target)
        targetInLowerHalf = self.binarySearch(minIndex,len(nums)-1,nums,target)

        if targetInUpperHalf == -1 and targetInLowerHalf == -1:
            return -1 
        else:
            return targetInUpperHalf if targetInUpperHalf != -1 else targetInLowerHalf

4. Full code
Copy

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        minIndex = self.findMin(nums)

      
        targetInUpperHalf = self.binarySearch(0,minIndex-1,nums,target)
        targetInLowerHalf = self.binarySearch(minIndex,len(nums)-1,nums,target)

        if targetInUpperHalf == -1 and targetInLowerHalf == -1:
            return -1 
        else:
            return targetInUpperHalf if targetInUpperHalf != -1 else targetInLowerHalf
        
    def findMin(self, nums):

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

        while left <= right:

            mid = left + (right - left) // 2


            #True
            InLowerHalf = nums[mid] <= nums[-1]
            if InLowerHalf:
                possibleMin = mid
                right = mid - 1

            #False
            else:
                left = mid + 1

        # returning the index instead the value
        return possibleMin 

    def binarySearch(self,left,right,nums,target):

        while left <= right:

            mid = right + (left-right) //2

            if target == nums[mid]:
                return mid

            elif target > nums[mid]:
                left = mid + 1

            elif target < nums[mid]:
                right = mid - 1

        # not found :(
        return -1

Sandbox—PythonTutor (Visualized)

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 lower half. O log(n)

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

Reframe problem 2.0 (For those that like a challenge)

Just a heads up: This has a lot of moving parts so bear with me.

3. In the previous part, we identified the minimum value and how it divided the array into two parts and used binary search on each of them. Is there a way to achieve the same result with just one logarithmic search?
4. In 📉The Minimum in a Rotated Sorted Array (2.d), we were able to find out on which half of the array we were on.
1. We can determine if we are in the upper or lower part of a rotated sorted array by comparing the element to the last element in the array. If the current element is greater than the last element, we are in the upper part; if it is smaller, we are in the lower part.
2. Can we do the same comparison for which half the target value as well as the midpoint value(the value we are on)?

3. Target in the lower half when it is less than or equal to the last element in the lower half of that array.

4. If we know the location of the target and the midpoint, we can identify four possible cases and use the comparison between the target and the midpoint to reduce the range by half and move closer to the target. There are two types of relationships between the target and the midpoint:
1. The target and the midpoint are in the same half of the array, there are two further cases:
1. Both in the upper half
2. Both in the lower half
2. Target and the midpoint are in different halves of the array, there are also two further cases
1. Target is in the upper half, mid is in the lower half
2. Target is in the lower half, mid is in the upper half
5. Let's first consider the case where the target and the midpoint are in the same half of the array - either both in the upper half or both in the lower half.
1. Let's look at whether both are in the upper half. There are two possibilities.
1. Target greater than the mid

1. We can disregard the elements on the left side of the mid since the target is greater than the mid and the array is sorted.

2. A case to be made: All the elements in the lower half are also lower than the target, so can we get rid of them? Not right now.
1. We don't have the boundary for these two arrays, i.e. the minimum point in the array, to make the call.
2. We always reduce the range from one side of the midpoint as we move closer to the target. Binary search does not involve reducing the range from both sides.
3. We won't be using a tactic like that in the next part, where the conditions will be suitable for a blitzkrieg of the whole lower half.
2. The target is less than the mid.

1. In this case, the target and the midpoint are both in the upper half, and the target is less than the mid so we can discard all elements that are greater than the midpoint as they would also be greater than the target. Additionally, we can also discard some elements that are lower than the midpoint(in the lower half), which is not usually done—we know that the target will not be present in the lower half so we can cut it. This allows us to keep the characteristic of a Binary search, wherein we eliminate the range of values from one side - in this case, all the values to the right of the midpoint are discarded, as the target will be located to the left.

2. When the target and the midpoint are in the lower half, there are two possible scenarios.
1. Target less than mid

2. All elements to the right of the midpoint will be discarded. Since we are in the lower half, the elements in the upper half are also irrelevant. However, as we discussed in binary search, we can only cut the range from one side, so the possibilities of that will not be aligned yet.

3. Target greater than mid.

4. Since both the midpoint and target are in the lower half, if the target is greater than the midpoint, all elements less than the midpoint are not relevant for the search. We can discard these elements, as well as the elements in the upper half since the target won't be found there either. Since both the elements less than the midpoint and the ones in the upper half are on the same side (the left side) of the midpoint, we can eliminate those, this follows the spirit of Binary Search, reducing the range from one side.

6. In light of the information above we can say that, if both the target and the mid are in the same half of the array, we can use an algorithm similar to 🍦Binary Search(Vanilla) .
1. If the target is greater than mid/target on the right side of the mid, we can disregard all values up to and including mid from the left.
2. Conversely, If the target is less than mid/target on the left side of the mid, we can disregard all values before and including mid from the right.
7. Code Snippet.
1. Where are the target and the mid?
Copy

# while loop 
# calculate mid

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

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

2. If both are in the same half.
Copy

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

8. This part is relatively simple. What if the target is on one side of the array and the midpoint is on the other side? In this case, there are two possible outcomes.
1. Target is in the upper half, mid is in the lower half.

1. We simply want to move the mid toward the upper half which happens to be on the right side. Simple as that.

2. Target is in the lower half, mid is in the upper half.

1. Same as above we will move the mid towards the right.

3. Code Snippet
Copy

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

9. One last thing. Since we are not using the 🔑Find the First True in a Sorted Boolean Array framework, as there are too many discrete cases, if we find the answer at any point we will return it.
Copy

if target == nums[mid]:
    return mid

Intuition 2.0

5. We cannot apply binary search directly since the array is not in sorted order, but separate the array into sides, where the target is and can’t be. Chop the one where it can’t be in our bid to shorten the range.
6. We can determine if the target and midpoint are located in the same array or not.
1. If both are in the same array:
1. We can reduce the problem to a standard Binary Search, which will also take care of the irrelevant halves.
2. If both are in separate arrays:
1. We can identify which half of the array contains the target, and move toward it.

Code

Copy

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
          
            
            targetInUpperHalf = target > nums[-1]
            targetInLowerHalf = target <= nums[-1] 
            
            midInUpperHalf = nums[mid] > nums[-1]
            midInLowerHalf = nums[mid] <= nums[-1]

           
        

            if target == nums[mid]:
                return mid     
            
            # Regular Binary Search
            if (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 -1

Slight Optimization

7. Since the constant values of targetInUpperHalf and targetInLowerHalf do not change inside the while loop, we can move them outside. This is beneficial since it allows us to make this query only once. If the query we are making was expensive, making an optimization like this can save a lot of time. Thus, if the values inside the loop do not change, we should move them outside.
Copy

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
    
        
        left,right = 0, len(nums)-1
				
				# OPTIMIZATION
				targetInUpperHalf = target > nums[-1] # <-- TO HERE
        targetInLowerHalf = target <= nums[-1] 
        
        while left <= right:

						# ALL OTHER CODE 

						# targetInUpperHalf = target > nums[-1] # <-- FROM HERE
            # targetInLowerHalf = target <= nums[-1] 
            
           
        return -1

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

Theoretically, this solution is the same as the first one, but this solution only requires running a logarithmic search once, instead of twice.

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

Dedications

https://www.youtube.com/watch?v=84a8fQp5hJA&ab_channel=Errichto