Leetcode 33. Search in Rotated Sorted Array

Problem

Leetcode 33 - Search in Rotated Sorted Array

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

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

Approach

This is similar version to Find Minimum in Rotated Sorted Array, we can solve this problem using Binary Search.

In a rotated array, there are 2 sorted subarrays. For example in our nums = [4,5,6,7,0,1,2], index 0-4 is sorted and rest are sorted. With this information we can check if target is in left side of array or right side of array.

• If nums[mid] == target, we just return
• If nums[left] to nums[mid] is sorted, meaning nums[left] <= nums[right]
  • If target < nums[left] OR target > nums[right], then it must mean that our target is in right side of the array thus move left pointer
  • Else, it must mean that our target is in the left side of the array thus move right pointer
• Else, this means that somewhere from nums[left] to nums[mid] it contains minimum value
  • If target < nums[mid] OR nums[right] < target, then it must mean that our target is in left side of the array thus move right pointer
  • Else, it must mean that our target is in the right side of the array thus move left pointer

Once it while loops is finished, it must mean that we don’t have target in list. Thus return -1

Visualization of the Approach:

nums = [4,5,6,7,0,1,2], target = 0
        l           r
nums[mid] = 7
Since nums[left] <= nums[mid], our middle is in left sorted portion
Since nums[left] > target, move our left pointer as our target is in right sorted portion

nums = [4,5,6,7,0,1,2]
                l   r
nums[mid] = 1
Since nums[left] <= nums[mid], our middle is in left sorted portion
Since target < nums[mid] AND target <= nums[left] move our right pointer as our target is in left sorted portion

nums = [4,5,6,7,0,1,2]
                l 
                r
nums[mid] = 0
Since we found our target, return its index.

return mid = 4

Here is the Python code for the solution:

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 left to mid is sorted
            if nums[left] <= nums[mid]:
                if nums[mid] < target or target < nums[left]
                    left = mid+1
                else:
                    right = mid-1
            else:
                if target < nums[mid] or nums[right] < target:
                    right = mid-1
                else:
                    left = mid+1
        
        return -1

Time Complexity and Space Complexity

Time Complexity: $O(log n)$

Space Complexity: $O(1)$