Find the Minimum in a Rotated Sorted Array

Find the Minimum in a Rotated Sorted Array

January 4, 2024
Binary Search

Problem #

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. The array may contain duplicates.

Example: Input: [3,4,5,1,2] Output: 1

Solution #

  • Algorithm: Modified Binary Search

Solution Approach:** #

- The idea is to use binary search. However, due to the rotation, a standard binary search won't work directly.
- The strategy is to find the inflection point where the order of the array changes.

Algorithm Steps:** #

1. Initialize `left` and `right` pointers to the start and end of the array.
2. While `left` is less than `right`, find the mid-point.
3. Check if the mid-point is the inflection point (where the order changes).
4. If the element at the mid is greater than the element at the right, it means the smallest value is to the right. So, move `left` to `mid + 1`.
5. Otherwise, move `right` to `mid`.
6. The minimum value is at the `left` index.

Python Code:** #

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

# Example Usage

Time Complexity:** #

- O(log N) in the average case, where N is the number of elements in the array. In the worst case (when elements are duplicates), it could be O(N).

Space Complexity:** #

- O(1), as only a constant amount of extra space is used.