Find the smallest value in a sorted array that has been rotated an unknown number of times.
You are given an integer array that was originally sorted in strictly increasing order, then rotated at an unknown pivot. The array contains no duplicate values.
Your task is to return the minimum element in the array.
A rotation means choosing some pivot index and moving the elements after it to the front while preserving their relative order.
Solve this in better than linear time if possible.
Input Format
- A single integer array
nums numscontains at least one element- All values are distinct
Output Format
- Return the minimum value present in
nums
Constraints
- Values are distinct
- The array is a rotation of a strictly increasing sorted array
Example 1
Input
nums = [3,4,5,1,2]
Output
1
Explanation
The original sorted array was [1,2,3,4,5], rotated so that 3,4,5 moved to the front. The minimum element is 1.
Example 2
Input
nums = [4,5,6,7,0,1,2]
Output
0
Explanation
The smallest value in the rotated array is 0.
Show 1 more example
Example 3
Input
nums = [11,13,15,17]
Output
11
Explanation
The array is not rotated, so the first element is the minimum.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.