Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array is a medium Binary Search problem from the Blind 75. The key pattern is binary search, and a good solution runs in O(log n) time.
Problem
Return the minimum value in a strictly increasing array that may have been rotated.
Examples
Example 1
Input
[30,40,50,5,10,20]Output
5Example 2
Input
[6,7,8,2,4]Output
2Example 3
Input
[21,23,25]Output
21Approach
Compare the middle value with the right end. If the middle is larger, the minimum lies to its right; otherwise it is at the middle or to its left.
| Pattern | Binary search |
|---|---|
| Time | O(log n) |
| Space | O(1) |
Watch out for
An array that was not rotated at all is also valid input.