Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] could become:
[3,4,5,6,1,2] if it was rotated 4 times [1,2,3,4,5,6] if it was rotated 6 times
Notice that rotating an array 4 times moves the last four elements of the array to the beginning. Rotating an array 6 times returns the original array.
Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.
A solution that runs in O(n) time is trivial. Can you write an algorithm that runs in O(log n) time?
Example 1:
Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1,2,3,4,5] and it was rotated 3 times.
Example 2:
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Recommended time and space complexity
You should aim for a solution with O(log n) time complexity and O(1) space complexity, where n is the size of the input array.
Hint 1
Linear search (O(n)) is simple, but can you use the fact that the array was originally sorted? Think about binary search.
Hint 2
The array is divided into two sorted parts. The minimum element is at the boundary of these parts. How can you find this boundary?
Hint 3
In binary search, compare the middle element with the right end. This will help determine which part contains the minimum.