Smallest Value in a Rotated Sorted Array
An array nums of distinct integers was first sorted in ascending order. Then it was rotated: some number of values were moved from the front to the back, keeping their order. The number of moved values is between 0 and n - 1.
Return the smallest value in nums.
Your solution should run in O(log n) time.
Hint
Compare the middle value with the last value of the current range. If the middle value is larger, the smallest value is somewhere to the right of the middle. If it is smaller, the smallest value is the middle itself or something to its left.
Examples
Example 1
- Input:
- [14,19,23,2,5,9]
- Output:
- 2
The sorted array [2, 5, 9, 14, 19, 23] had its first three values moved to the back. The smallest value, 2, is now at index 3.
Example 2
- Input:
- [-8,-3,0,6]
- Output:
- -8
The array was not rotated, so the smallest value is the first one.
Example 3
- Input:
- [7,1]
- Output:
- 1
The sorted array [1, 7] was rotated by one, so 1 moved to the end.
Constraints
1 <= nums.length <= 40-1000 <= nums[i] <= 1000- All values in
numsare different. numsis an ascending array rotated by some amount (possibly zero).
Run checks your code against the 3 examples. Submit checks it against all 253 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.