Find the Minimum in a Rotated Sorted Array

January 4, 2024

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:** #

```python
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
        else:
            right = mid
    return nums[left]

# Example Usage
print(findMin([3,4,5,1,2]))
```

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.