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.

You must 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, the minimum element will be the only element that is smaller than its predecessor (if we consider the array to be circular). We can leverage this property to perform a binary search:

1. Initialize: Set left to 0 and right to len(nums) - 1.
2. Binary Search: While left < right:
   • Calculate mid = (left + right) // 2.
   • Check for minimum: If nums[mid] > nums[right], the minimum element lies in the right half (because the right half is still sorted and larger than the middle). Set left = mid + 1.
   • Otherwise, the minimum element lies in the left half (including mid), so set right = mid.
3. Return: After the loop, left and right will converge to the index of the minimum element. Return nums[left].

Explanation

The algorithm works because it efficiently eliminates half of the search space in each iteration. The comparison nums[mid] > nums[right] determines whether the minimum element is in the left or right half.

• If nums[mid] > nums[right], it means the right half is still in its original sorted order and the minimum must be in the right half because the minimum element is always smaller than its adjacent right element.

• If nums[mid] <= nums[right], it implies the minimum element is in the left half (or at mid).

Code

def findMin(nums):
    """
    Finds the minimum element in a rotated sorted array using binary search.

    Args:
        nums: A list of integers.

    Returns:
        The minimum element in the array.
    """
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (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) because we use only a constant amount of extra space.