Find Minimum in Rotated Sorted Array

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 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in $O(\log n)$ time.

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times (which is the same as 0 times).

Approach: Modified Binary Search

Because the array was originally sorted and then rotated, it is conceptually divided into two sorted portions: a left sorted portion and a right sorted portion.
Crucially, all elements in the left sorted portion are strictly greater than all elements in the right sorted portion (unless the array is not rotated at all).

We can use Binary Search to find the minimum element in $O(\log n)$ time:

1. Initialize left = 0, right = nums.length - 1. Let res = nums[0].
2. Loop while left <= right:
   • Optimization Check: If the current search space nums[left...right] is already strictly sorted (meaning nums[left] < nums[right]), then the minimum in this space is simply nums[left]. We can update res = Math.min(res, nums[left]) and break out of the loop early.
   • Otherwise, calculate the mid index: mid = Math.floor((left + right) / 2).
   • Update our res with the value at mid: res = Math.min(res, nums[mid]).
   • Now we must decide which half to search next:
     • If nums[mid] >= nums[left]: This means mid belongs to the left sorted portion. Since all values in the left sorted portion are greater than the right sorted portion, the absolute minimum must be somewhere to the right of mid. We search the right half: left = mid + 1.
     • If nums[mid] < nums[left]: This means mid belongs to the right sorted portion. The absolute minimum could be at mid (which we already checked) or somewhere to its left. We search the left half: right = mid - 1.
3. Return res.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function findMin(nums) {
    let left = 0;
    let right = nums.length - 1;
    let res = nums[0];
    
    while (left <= right) {
        // If the current search space is fully sorted, 
        // the left-most element is the minimum.
        if (nums[left] < nums[right]) {
            res = Math.min(res, nums[left]);
            break;
        }
        
        let mid = Math.floor((left + right) / 2);
        res = Math.min(res, nums[mid]);
        
        // Is mid in the left sorted portion?
        if (nums[mid] >= nums[left]) {
            // Search right half
            left = mid + 1;
        } else {
            // Search left half
            right = mid - 1;
        }
    }
    
    return res;
}

Complexity Analysis

• Time Complexity: $O(\log n)$ where $n$ is the number of elements in the nums array. We divide the search space in half at each step.
• Space Complexity: $O(1)$. We only use a few integer variables for pointers and the result, so the space complexity is constant.