Find Minimum in Rotated Sorted Array
Suppose an array of distinct integers is sorted in ascending order and rotated an unknown number of times. Given the rotated array, find the minimum element.
Constraints:
- 1 <= nums.length <= 5000
- -5000 <= nums[i] <= 5000
- nums is sorted in ascending order and rotated an unknown number of times
Examples:
Input: [3,4,5,1,2]
Output: 1
Explanation: The minimum element is 1, which is the first element in the unrotated array [1,2,3,4,5].
Input: [4,5,6,7,0,1,2]
Output: 0
Explanation: The minimum element is 0, which is the first element in the unrotated array [0,1,2,4,5,6,7].
Input: [11,13,15,17]
Output: 11
Explanation: The minimum element is 11, which is the first element in the unrotated array [11,13,15,17].
Solutions
Binary Search
We use binary search to find the minimum element in the rotated array. We maintain two pointers, left and right, to represent the current search range. In each iteration, we calculate the middle index and compare the middle element with the rightmost element. If the middle element is greater than the rightmost element, we know that the minimum element must be in the right half of the array, so we update the left pointer to mid + 1. Otherwise, we update the right pointer to mid. We repeat this process until left and right pointers meet, which is the index of the minimum element.
def findMin(nums):
left, right = 0, len(nums) - 1; while left < right:
mid = (left + right) // 2; if nums[mid] > nums[right]:
left = mid + 1; else:
right = mid; return nums[left]Follow-up:
What if the array is not rotated, how would you find the minimum element?
