Binary Search Searching a sorted array
235. Find Minimum in Rotated Sorted Array
You are given an array nums of distinct integers. It was made by sorting some integers in increasing order
and then rotating the sorted array some number of times. Return the smallest value in nums.
Rotating an array once moves its last element to the front. For example, rotating [2, 4, 6, 8, 10] twice
gives [8, 10, 2, 4, 6]. The number of rotations can be zero, so nums may still be sorted.
Aim for O(log n) time.
Example 1
Input: nums = [15, 22, 37, 41, -8, -3, 0, 9]
-8Explanation: The sorted array [-8, -3, 0, 9, 15, 22, 37, 41] was rotated four times, so its last four values moved to
the front. The smallest value, −8, now sits at position 4, right after the largest value, 41.
Example 2
Input: nums = [3, 5, 8, 13, 21]
3Explanation: The array was rotated zero times. It is still sorted, so the smallest value is the first one.
Example 3
Input: nums = [-4, -1, 6, 12, -20]
-20Explanation: The sorted array [-20, -4, -1, 6, 12] was rotated four times. That moved every value except −20 to the
front, so the smallest value is now the last element.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-231 ≤ nums[i] ≤ 231 − 1- All values in
numsare distinct. numsis an array sorted in increasing order and then rotated between 0 andnums.length − 1times.
Clarifying questions
What you would ask an interviewer before writing any code.