Algorithm Day68 - Find Minimum in Rotated Sorted Array

Posted on In , Views:

🧩 Problem Description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times.

For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if rotated 4 times.
  • [0,1,2,4,5,6,7] if rotated 7 times.

Given the rotated sorted array nums of unique elements, return the minimum element of this array.

You must write an algorithm with O(log n) runtime complexity.

💬 Examples

Example 1

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

Example 2

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

Example 3

1
2
Input: nums = [11,13,15,17]
Output: 11

💡 Intuition

The minimum value is the “pivot point” where rotation happens.

  • If nums[mid] > nums[right], the minimum lies in the right half.
  • Otherwise, it lies in the left half (including mid).

This ensures O(log n) with binary search. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

⏱ Complexity Analysis

  • Time: O(log n) — binary search.
  • Space: O(1) — constant space.

✍️ Summary

  • Use binary search to find the pivot (minimum element).
  • Compare nums[mid] with nums[right] to decide which half to search.

Related problems

  • lc-33 — Search in Rotated Sorted Array
  • lc-154 — Find Minimum in Rotated Sorted Array II