Search in Rotated Sorted Array

Problem Statement

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

Approach: Modified Binary Search

Even though the array is rotated, we can still use Binary Search. The key insight is that if you divide a rotated sorted array in half, at least one of the two halves will always be strictly sorted.

By identifying which half is sorted, we can check if our target falls within that half’s range.

1. Initialize two pointers: left = 0 and right = nums.length - 1.
2. Loop while left <= right:
   • Calculate the middle index: mid = Math.floor((left + right) / 2).
   • If nums[mid] is equal to the target, we found it! Return mid.
   • Determine which half is properly sorted:
     • Is the Left Half Sorted? (i.e., nums[left] <= nums[mid])
       • Check if the target falls within this sorted left boundary: nums[left] <= target && target < nums[mid].
       • If it does, then the target must be in the left half, so we update right = mid - 1.
       • If it does not, then the target must be in the right half, so we update left = mid + 1.
     • Otherwise, the Right Half is Sorted! (i.e., nums[mid] < nums[right])
       • Check if the target falls within this sorted right boundary: nums[mid] < target && target <= nums[right].
       • If it does, then the target must be in the right half, so we update left = mid + 1.
       • If it does not, then the target must be in the left half, so we update right = mid - 1.
3. If the loop completes without returning, the target doesn’t exist in the array. Return -1.

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function search(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) {
            return mid;
        }
        
        // Check if the left half is the sorted portion
        if (nums[left] <= nums[mid]) {
            // Is target within the sorted left half?
            if (target >= nums[left] && target < nums[mid]) {
                right = mid - 1; // Search left half
            } else {
                left = mid + 1; // Search right half
            }
        } 
        // Otherwise, the right half must be the sorted portion
        else {
            // Is target within the sorted right half?
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
    }
    
    return -1;
}

Complexity Analysis

• Time Complexity: $O(\log n)$ where $n$ is the number of elements in the nums array. We eliminate half of the remaining elements at each step, just like a standard binary search.
• Space Complexity: $O(1)$. The variables left, right, and mid only use a constant amount of extra space.