Find Minimum in Rotated Sorted Array

You get a vector nums of different integers.

Return the smallest number in nums.

The numbers were sorted from smallest to largest. Then the array may have been rotated. A rotation moves the first k numbers to the end, in the same order. Here 0 <= k < nums.size().

For example, [1,4,6,9] with k = 1 becomes [4,6,9,1]. With k = 0, nothing moves.

Example 1:

Input: nums = [21,30,4,9,16]
Output: 4
Explanation: The sorted array was rotated with k = 3.
So 4, 9 and 16 moved to the end.
The smallest number is 4.

Example 2:

Input: nums = [-6,-2,5,12]
Output: -6
Explanation: This array was not rotated (k = 0).
The first number is the smallest.

Example 3:

Input: nums = [40,-5]
Output: -5

Constraints:

• 1 to 1,000,000 numbers.
• All numbers are different.
• Each number is from -10⁹ to 10⁹.
• The array is sorted, then maybe rotated (see above).