Find Minimum in Rotated Sorted Array
MediumBinary Search
An array of unique integers was sorted in ascending order and then rotated: some number of elements were moved, in order, from the front to the back. For example, [1, 2, 3, 4, 5] rotated by 2 becomes [3, 4, 5, 1, 2]. The rotation amount can be anything from 0 to n - 1, so the array may still be fully sorted.
Given the rotated array nums, return its smallest value.
Your solution must run in O(log n) time.
Example 1
- Input:
- nums = [0,3,9,-8,-4]
- Output:
- -8
- Explanation
- The original order was
[-8, -4, 0, 3, 9], rotated so it now starts at 0. The value right after the drop from 9 to -8 is the minimum.
Example 2
- Input:
- nums = [4,5,6,1,2,3]
- Output:
- 1
- Explanation
- The array climbs 4, 5, 6 and then drops to 1. The drop marks where the original sorted array started, so 1 is the smallest.
Example 3
- Input:
- nums = [2,5,8,13]
- Output:
- 2
- Explanation
- This array was rotated by its full length (or not at all), so it is still sorted and the first element is the minimum.
Constraints
1 <= nums.length <= 5000-5000 <= nums[i] <= 5000- All values in
numsare unique numsis a sorted array rotated between0andn - 1times