Find Minimum in Rotated Sorted Array

You are given a sorted array that has been rotated at some unknown pivot point. This means the array was initially sorted in ascending order, but then a portion of it was moved from the beginning to the end. Your task is to find the minimum element in this rotated sorted array. This problem is useful in scenarios where you have a large, sorted dataset that has been partially corrupted or rearranged, and you need to efficiently locate the smallest value.

Problem Description

The problem requires you to identify the minimum element within a rotated sorted array. The array consists of distinct integers. The rotation point is unknown. You must implement an algorithm that efficiently finds the minimum value without fully sorting the array.

What needs to be achieved:

• Given a rotated sorted array, determine the minimum element present in the array.

Key requirements:

• The array is initially sorted in ascending order.
• The array has been rotated at some unknown pivot point.
• All elements in the array are distinct.

Expected behavior:

• The function should return the minimum element in the array.
• The function should handle edge cases such as an empty array or an array with only one element.

Edge cases to consider:

• Empty array: Return null or an appropriate error value (depending on language conventions).
• Array with one element: Return that element.
• Array that is not rotated (already sorted): Return the first element.
• Array rotated such that the minimum element is at the beginning.
• Array rotated such that the minimum element is in the middle.
• Array rotated such that the minimum element is at the end.

Examples

Example 1:

Input: [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The array was originally sorted as [0, 1, 2, 4, 5, 6, 7] and then rotated. The minimum element is 0.

Example 2:

Input: [3, 4, 5, 1, 2]
Output: 1
Explanation: The array was originally sorted as [1, 2, 3, 4, 5] and then rotated. The minimum element is 1.

Example 3:

Input: [11, 13, 15, 17]
Output: 11
Explanation: The array is already sorted and not rotated. The minimum element is 11.

Example 4:

Input: [2,1]
Output: 1
Explanation: Simple rotation.

Constraints

• The length of the array will be between 1 and 10,000 inclusive.
• Each element in the array will be an integer.
• All elements in the array are distinct.
• The algorithm should have a time complexity of O(log n). A linear search (O(n)) will not be accepted.

Notes

Consider using a binary search approach to efficiently find the minimum element. The key idea is to compare the middle element with the first element to determine which half of the array is sorted and which half contains the minimum element. Be mindful of how the rotation affects the comparison logic. Think about how to handle cases where the left and right subarrays are both sorted.