Leetcode 33 - Search in Rotated Sorted Array

Table of contents

Problem

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

Explanation/Approach

Given a sorted and rotated array, the goal is to find the index of a target value efficiently (with O(log n) time complexity). To achieve logarithmic time complexity, we can use a modified version of binary search.

The primary challenge here is dealing with the rotation in the array. First, identify whether the target value resides in the rotated part or the sorted part of the array. Then proceed with binary search in the identified subarray.

• Step 1: Find the middle element of the array.
• Step 2: Determine which part of the array is sorted (either the left or right half).
• Step 3: Check if the target resides within the sorted part. If so, discard the other half. If not, discard the sorted half.
• Step 4: Repeat the process until you find the target or the search space is empty.

Solution (Modified Binary Search)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Define the start and end pointers
        start = 0
        end = len(nums) - 1

        # Continue the search while start is less than or equal to end
        while start <= end:
            mid = start + (end - start) // 2  # Find the middle element

            # If target is found, return its index
            if nums[mid] == target:
                return mid

            # Determine if left half is sorted
            if nums[start] <= nums[mid]:
                # If target is in the sorted left half, update end pointer
                if nums[start] <= target <= nums[mid]:
                    end = mid - 1
                # Otherwise, update start pointer
                else:
                    start = mid + 1
            # If right half is sorted
            else:
                # If target is in the sorted right half, update start pointer
                if nums[mid] <= target <= nums[end]:
                    start = mid + 1
                # Otherwise, update end pointer
                else:
                    end = mid - 1

        # If target is not found, return -1
        return -1

Explanation

• Set start and end pointers at the beginning and end of nums.
• Enter a loop that continues as long as start is less than or equal to end.
• Calculate the mid index and check if nums[mid] is the target. If yes, return mid.
• Check which half of the array is sorted by comparing nums[start] and nums[mid].
• Determine if the target is within the sorted half by comparing it with nums[start] and nums[mid] (or nums[mid] and nums[end] for the right half).
• If target is in the sorted half, adjust start or end to search within it; otherwise, search in the other half.
• Repeat the process until start exceeds end or the target is found.

Time and Memory Complexity

• Time Complexity: O(log n) due to the modified binary search algorithm that reduces the search space in half with each iteration.
• Space Complexity: O(1), since the algorithm uses a constant amount of space regardless of the input size.