Find Minimum In Rotated Sorted Array

Medium · Binary Search

You are given an array of distinct integers that was originally sorted in increasing order and then rotated some unknown number of times to the right. Return the smallest value in the array. You must reason about the array without knowing the rotation point in advance.

Examples

Input:  nums = [3,4,5,1,2]
Output: 1
Why:    The array was sorted [1,2,3,4,5] then rotated so that 1 is now the minimum located after the rotation point.

Input:  nums = [4,5,6,7,0,1,2]
Output: 0
Why:    0 is the smallest element, sitting right after the point where the sequence wraps around.

Input:  nums = [11,13,15,17]
Output: 11
Why:    The array happens to have zero effective rotation, so the first element is already the minimum.

Constraints

1 <= nums.length <= 5000, -5000 <= nums[i] <= 5000, all values in nums are unique, and nums is a rotated version of some ascending sorted array.

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Find Minimum In Rotated Sorted Array

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Find Minimum In Rotated Sorted Array. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.