MediumArrayBinary Search

Find Minimum in Rotated Sorted Array

1 approach, code in all languages

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 unlock the solution

See 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

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI