Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

Problem Description
Suppose an array sorted in ascending order is rotated at some unknown pivot (e.g., the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Design an algorithm with O(log n) time complexity to find the minimum element in the rotated array. The array does not contain duplicate elements.

Key Points Analysis

  1. The rotated array consists of two sorted segments; the minimum element is the starting point of the second sorted segment.
  2. Direct traversal of the array requires O(n) time, but the problem demands O(log n), hinting at the use of binary search.
  3. The absence of duplicate elements ensures the reliability of binary search.

Solution Steps

1. Understand the Property of Rotated Arrays
The rotated array is divided into two parts: the left segment (larger values) and the right segment (smaller values). For example, [4,5,6,7,0,1,2]:

  • Left segment: [4,5,6,7] (all values ≥ the first element of the left segment, 4)
  • Right segment: [0,1,2] (all values < the first element of the left segment, 4)
    The minimum is the first element of the right segment, and its index is called the pivot.

2. Binary Search Approach

  • Set left boundary left = 0 and right boundary right = n-1.
  • Compare the middle element nums[mid] with the right boundary element nums[right]:
    • If nums[mid] < nums[right]: It means mid is in the right segment (the smaller segment), and the minimum is to the left of mid (including mid). Shrink the right boundary: right = mid.
    • If nums[mid] > nums[right]: It means mid is in the left segment (the larger segment), and the minimum is to the right of mid (excluding mid). Shrink the left boundary: left = mid + 1.
  • Termination condition: left == right, at which point it points to the minimum element.

3. Step-by-Step Example Walkthrough
Array: [4,5,6,7,0,1,2]

  1. left=0, right=6 → mid=3 (value 7)
    • Compare: 7 > 2 (mid in left segment) → left = mid+1 = 4
  2. left=4, right=6 → mid=5 (value 1)
    • Compare: 1 < 2 (mid in right segment) → right = mid = 5
  3. left=4, right=5 → mid=4 (value 0)
    • Compare: 0 < 2 (right segment) → right = mid = 4
  4. left=4, right=4 → End, minimum nums[4]=0.

4. Why Compare with the Right Boundary Instead of the Left?

  • Comparing nums[mid] with nums[right] clearly determines whether mid is in the left or right segment:
    • The right segment is always less than or equal to the right boundary (since it's sorted in ascending order).
  • If comparing with the left boundary nums[left], additional handling is needed for the unrotated array case (e.g., [0,1,2]), which increases complexity.

5. Code Implementation (Python)

def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < nums[right]:
            right = mid
        else:
            left = mid + 1
    return nums[left]

6. Complexity Analysis

  • Time complexity: Each iteration halves the search range, O(log n).
  • Space complexity: O(1).

Summary
By using binary search to compare the middle element with the right boundary, the pivot can be efficiently located. The key idea is to leverage the segmented sorted property of the rotated array to quickly narrow down the search range through comparisons.