A list of n different numbers was sorted from small to large. Then it was rotated: the last number was moved to the front, and this was repeated some number of times (from 1 to n times). So the smallest number can now be anywhere in the list.
For example, [10,20,30,40,50] rotated 2 times becomes [40,50,10,20,30].
Given the rotated list nums, return its smallest number. Your solution must take O(log n) time.
Examples
Example 1:
Input: nums = [6,7,8,1,2,3,4,5]
Output: 1
Explanation: The sorted list 1 to 8 was rotated 3 times. The smallest number is 1.
Example 2:
Input: nums = [20,25,5,10,15]
Output: 5
Explanation: The sorted list 5, 10, 15, 20, 25 was rotated 2 times. The smallest number is 5.
Example 3:
Input: nums = [3,9,14]
Output: 3
Explanation: Rotating a list of length 3 exactly 3 times gives the same list back. The smallest number is the first one.