Search in Rotated Sorted Array

Binary Search

Problem

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.

For example:

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

Thought Process

• Because the array is not fully sorted, we can't apply regular binary search (because the ranges are all messed up since it is rotated)

• Since the array was sorted in ascending order before it was rotated, we can utliize this fact to look in between the ranges of the the rotated array to see which half is sorted.

Solution

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums)-1
        
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] <= nums[high]:
                if target > nums[mid] and target <= nums[high]:
                    low = mid+1
                else:
                    high = mid - 1 #the case where target is less than mid
            elif nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid+1
        return -1

Follow up:

What if the array contained duplicates?

• If the array contains duplicates, the mid will be the same as the low index (we know this because the array is sorted in ascending order). If this is the case, we just keep increasing low index.To explain why, consider this sorted array 1111115, which is rotated to 1151111 . Assume left = 0 and mid = 3, and the target we want to search for is 5. Therefore, the condition A[left] == A[mid] holds true. We need to keep increasing the lower index.

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        low, high = 0, len(nums)-1
        
        while low <= high:
            mid = low + (high-low)//2
            if nums[mid] == target:
                return True
            
            elif nums[mid] == nums[low]:
                low+=1
            
            elif nums[mid] <= nums[high]:
                if target > nums[mid] and target <= nums[high]:
                    low = mid+1
                else:
                    high = mid - 1 #the case where target is less than mid
            elif nums[low] <= nums[mid]:
                if target >= nums[low] and target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid+1
        return False
            
        

Key Points

• This problem is all about searching in the right sorted range.

• We need to check if the ranges are increasing and if so, check if the target fits between those ranges

• If our array contauns duplicates, the mid will be the same as low so we must increase the lower index.

Time Complexity

• Time: $O(log(n))$

• Space: $O(1)$