Find Minimum in Rotated Sorted Array

You get an array 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.Length.

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).