MediumArrayBinary Search

Find Minimum in Rotated Sorted Array

1 approach, code in every language

Imagine an array that was originally sorted in ascending order and then rotated to the left some unknown number of times, so a slice of the front got moved to the back. Every element is unique. Your job is to return the smallest value that remains hidden somewhere inside this rotated arrangement.

A sweep across all elements would obviously work, but the array's structure lets you discard half of the remaining candidates at each step, so an efficient solution should run in logarithmic time.

Example 1

Input: nums = [3,4,5,1,2]

Output: 1

The original [1,2,3,4,5] was rotated so the minimum 1 landed in the middle.

Example 2

Input: nums = [4,5,6,7,0,1,2]

Output: 0

After rotation the smallest value 0 sits at index 4.

Constraints

n == nums.length
1 ≤ n ≤ 5000
-5000 ≤ nums[i] ≤ 5000
All integers in nums are unique

Binary Search Against the Right Edge

Compare the midpoint with the rightmost element to decide which half still contains the minimum.

Loading animation…

Intuition

In a rotated sorted array the minimum is the single point where a larger value is immediately followed by a smaller one. Comparing the midpoint to the current right endpoint tells us which side we are on: if the midpoint is bigger than the right edge, the dip must be to the right of mid, otherwise the minimum is at mid or to its left. Narrowing the window this way converges on the pivot.

Algorithm walkthrough

1Set lo to the first index and hi to the last index.
2While lo is below hi, compute the midpoint.
3If the midpoint value exceeds the value at hi, the minimum lies strictly right, so set lo to mid + 1.
4Otherwise the minimum is at mid or to its left, so set hi to mid.
5When the window shrinks to one slot, that element is the minimum.

Implementation

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]

Time

O(log n)

Space

O(1)

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Wrapped Buoy Low Offset is our own problem on the technique behind Find Minimum in Rotated Sorted Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free