Intermediate Level
Implement the findMinimumRotatedSorted method that returns the minimum value from a rotated sorted array.
The input contains a rotated sorted integer array nums and its length size. Your task is to return the minimum value in the array.
A rotated sorted array was originally sorted in ascending order, but some leading elements were moved to the end. The smallest value is the rotation point.
For example, in [3,4,5,1,2], the minimum value is 1.
Example 1
Input
nums (int[]) =
[3,4,5,1,2]size (int) =
5Returns (int)
1Example 2
Input
nums (int[]) =
[4,5,6,7,0,1,2]size (int) =
7Returns (int)
0Example 3
Input
nums (int[]) =
[11,13,15,17]size (int) =
4Returns (int)
11Use binary search by comparing the middle value with the rightmost value.
If nums[mid] is greater than nums[right], the minimum value must be on the right side of mid. Otherwise, the minimum value is at mid or somewhere on the left side.
Continue narrowing the range until both pointers meet. The value at that position is the minimum.
Pseudocode:
function findMinimumRotatedSorted(nums, size):
left = 0
right = size - 1
while left < right:
mid = left + (right - left) / 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run