Problem Description
Given an array of length n sorted in ascending order that has been rotated between 1 and n times, return the minimum element of this array. The array contains unique elements.
Key Insights
- The array is originally sorted but rotated, leading to two sorted subarrays.
- The minimum element will be the point where the order breaks.
- A binary search can efficiently locate the minimum element in O(log n) time.
Space and Time Complexity
Time Complexity: O(log n)
Space Complexity: O(1)
Solution
The problem can be solved using a modified binary search algorithm. The idea is to maintain two pointers, left and right, which represent the current search boundaries. By comparing the middle element with the rightmost element, we can decide which half of the array to search next. If the middle element is greater than the rightmost element, it indicates that the minimum must be in the right half. Otherwise, it is in the left half. This process continues until the minimum element is found.