Find Minimum 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.

Write a function to find the minimum element in the rotated 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] rotated 4 times.

Steps

The key to solving this problem efficiently is using binary search. Since the array is rotated, there's a point where the array is "broken." The minimum element will be the smallest element to the right of the "break" point. We can exploit this property with binary search:

1. Initialize: Set left = 0 and right = nums.length - 1.
2. Binary Search: While left < right:
   • Calculate mid = floor((left + right) / 2).
   • Case 1: nums[mid] > nums[right]: The minimum element is in the right half of the array (because the right half contains the "broken" part). Update left = mid + 1.
   • Case 2: nums[mid] <= nums[right]: The minimum element is in the left half of the array (including mid). Update right = mid.
3. Return: After the loop, left and right will point to the minimum element. Return nums[left].

Explanation

The logic behind the binary search conditions is crucial:

• nums[mid] > nums[right]: If the middle element is greater than the rightmost element, it means the minimum element must lie in the right half. This is because the right half represents the portion of the sorted array that has been rotated. The minimum element is always at the boundary of the rotated and unrotated parts.

• nums[mid] <= nums[right]: If the middle element is less than or equal to the rightmost element, it means the minimum element must lie in the left half (or potentially at mid). The right half is sorted in ascending order, hence the minimum cannot be there.

By repeatedly applying this logic, the binary search effectively narrows down the search space until only the minimum element remains.

Code

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

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

        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return nums[left];
};

Complexity

• Time Complexity: O(log n) due to the binary search.
• Space Complexity: O(1) as we are using only a constant amount of extra space.