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.

Additional information

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Binary Search

Intuition

Since the array is sorted but rotated, we can view it as two sorted subarrays joined together. The minimum element is the only element that is smaller than its previous element (the "pivot" point). Because the array is partially sorted, we can use Binary Search.

1. The Concept:
In a standard sorted array, the element at the right end is always the largest. In a rotated array, if the middle element is greater than the element at the right end, we know the rotation (and thus the minimum element) happens in the right half.

2. The Comparison:
We compare nums[mid] with nums[right]:

• **Case 1: nums[mid] > nums[right]**:

• This implies the "cliff" (drop from max to min) is somewhere to the right of mid.

• Example: [3, 4, 5, 1, 2]. Mid is 5, Right is 2. 5 > 2. We search right (l = m + 1).

• **Case 2: nums[mid] < nums[right]**:

• This implies the right half is sorted and the minimum is either at mid or to its left.

• Example: [5, 1, 2, 3, 4]. Mid is 2, Right is 4. 2 < 4. We search left, but keep mid as a candidate (r = m).

Algorithm

Step 1: Initialize two pointers: l = 0 and r = len(nums) - 1.

Step 2: Start a loop that continues while l < r. (We use < instead of <= because we stop when l and r converge on the single minimum element).

Step 3: Calculate the middle index: m = (l + r) // 2.

Step 4: Compare the value at the middle nums[m] with the value at the right boundary nums[r].

Step 5: If nums[m] > nums[r], it means the minimum value is in the right part of the array. Set l = m + 1.

Step 6: If nums[m] <= nums[r], it means the minimum value is at m or in the left part. Set r = m.

Step 7: When the loop ends (l == r), nums[l] will be the minimum value. Return it.

def find_min(nums: list[int]) -> int:
    l, r = 0, len(nums) - 1
    
    while l < r:
        m = (l + r) // 2
        # If the middle element is greater than the rightmost element,
        # the minimum must be to the right of mid.
        if nums[m] > nums[r]:
            l = m + 1
        # Otherwise, the minimum is at mid or to the left.
        else:
            r = m
            
    return nums[l]

Time & Space Complexity

• Time Complexity: O(log n). We cut the search space in half during each iteration.
• Space Complexity: O(1). We only use pointers.