Find Minimum in Rotated Sorted Array

Master this topic with zero to advance depth.

Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in $O(\\log N)$ time.

Medium

Examples

Input: nums = [3,4,5,1,2]
Output: 1
The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [4,5,6,7,0,1,2]
Output: 0
The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Approach 1

Level I: Brute Force (Linear Scan)

Intuition

Simply scan the array and find the minimum element. We don't exploit the sorted/rotated property.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

nums = [3,4,5,1,2]. Min starts at 3. Compare with 4, 5, 1 (new min), 2. Result: 1.

java

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int n : nums) if (n < min) min = n;
        return min;
    }
}

Approach 2

Level III: Optimal (Binary Search)

Intuition

In a rotated sorted array, if nums[mid] > nums[right], the minimum must be in the right half (excluding mid). Otherwise, it's in the left half (including mid).

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

Step	L	R	Mid	nums[Mid]	nums[R]	Decision
1	0	4	2	5	2	5 > 2 → L = 3
2	3	4	3	1	2	1 < 2 → R = 3
Exit	3	3	-	-	-	Return nums[3] = 1

java

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) l = mid + 1;
            else r = mid;
        }
        return nums[l];
    }
}

← Previous QuestionFind Peak Element

Next Question →Search in Rotated Sorted Array

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.