Search in Rotated Sorted Array medium

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 0 times.

You are given a rotated sorted array nums of unique elements, and an integer target. Write a function to determine if the target exists in the array. If it does, return its index; otherwise, return -1. You must write an efficient 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

Steps

The key to solving this problem efficiently is using binary search, but modified to account for the rotation. The standard binary search assumption that the left half is always smaller than the right half is no longer valid. Here's a breakdown of the algorithm:

1. Find the pivot: The pivot is the index where the rotation occurred. It's the index of the smallest element in the array. We can find this by comparing the middle element with the rightmost element. If the middle element is smaller, the pivot lies in the left half; otherwise, it's in the right half.

2. Binary Search with Pivot Awareness: Once we have a rough idea of where the pivot is (or even if it's not rotated), we perform a modified binary search:

   • If nums[mid] == target, we found it!
   • If the left half is sorted (i.e., nums[left] <= nums[mid]):
     • If target is within the range of the left half (nums[left] <= target <= nums[mid]), search the left half.
     • Otherwise, search the right half.
   • If the right half is sorted (i.e., nums[mid] <= nums[right]):
     • If target is within the range of the right half (nums[mid] <= target <= nums[right]), search the right half.
     • Otherwise, search the left half.

3. Handle edge cases: Consider empty arrays or arrays with a single element.

Explanation

The algorithm leverages the fact that even though the array is rotated, at least one of the halves (left or right) will always be sorted. By intelligently determining which half is sorted and checking if the target falls within that sorted half's range, we can efficiently eliminate half of the search space in each iteration, maintaining the O(log n) complexity of binary search.

Code (Typescript)

function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        // Check if the left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else { // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    return -1; // Target not found
}

Complexity

• Time Complexity: O(log n) due to the binary search approach.
• Space Complexity: O(1) because the algorithm uses a constant amount of extra space.