153. Find Minimum in Rotated Sorted Array

Question

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 it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

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.

Example1

Input: nums = [3, 4, 5, 1, 2]
Output: 1 -> the minimum element
Explanation: The original array was [1, 2, 3, 4, 5] rotated 3 times.

Example2

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

Example3

Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: The original array was [11, 13, 15, 17] and it was rotated 4 times. 

Constraints

• $n == nums.length$
• $1 <= n <= 5000$
• $-5000 <= nums[i] <= 5000$
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Solution: Binary Search

• Time Complexity: $O(log n)$
• Space Complexity: $O(1)$

public int findMin(int[] nums) {
    int l = 0;
    int r = nums.length - 1;

    // Loop until one element remains
    while (l < r) {
        
        // Prevent integer overflow
        int m = l + (r - l) / 2;

        // Case 1: Right half is sorted. Min is in [l...m]
        if (nums[m] < nums[r]) {
            r = m;
        } 
        // Case 2: Pivot (drop) is in the right half. Min is in [m+1...r]
        else {
            l = m + 1;
        }
    }

    return nums[l];
}

Dry Run

• Array: nums = [4, 5, 6, 7, 0, 1, 2]
• Indices: 0, 1, 2, 3, 4, 5, 6
• Goal: Find the minimum element (Target: 0)

Iteration	Left (l)	Right (r)	Mid (m)	Compare (nums[m] vs nums[r])	Logic & Action
1	0	6	3	7 > 2 (True)	The middle element (7) is greater than the rightmost element (2). This means the rotation pivot (drop) is in the right half. → Action: l = m + 1 (New l = 4)
2	4	6	5	1 < 2 (False)	The middle element (1) is smaller than the rightmost element (2). The right side is sorted. The minimum is either at mid or to its left. → Action: r = m (New r = 5)
3	4	5	4	0 < 1 (False)	The middle element (0) is smaller than the rightmost element (1). The right side is sorted. → Action: r = m (New r = 4)
End	4	4	-	-	l == r. The loop terminates. Return nums[4] which is 0.

Key Essence

1. The True Condition for Binary Search

The prerequisite for Binary Search is not necessarily “Global Sorting,” but rather “The ability to make a binary decision.”

As long as we can establish a logical rule (a predicate) that allows us to confidentially discard half of the search space, Binary Search is valid. In this problem, even though the array isn’t fully sorted, it preserves partial monotonicity, which gives us that logical rule.

2. Visualizing the Structure: “Two Slopes and a Cliff”

If we plot the values of a rotated sorted array (e.g., [4, 5, 6, 7, 0, 1, 2]), we don’t see a random scatter of numbers. Instead, we see two ascending slopes separated by a single drop (cliff).

• Left Slope (Higher values): e.g., [4, 5, 6, 7]
• Right Slope (Lower values): e.g., [0, 1, 2]
• The Target: The minimum element (0) sits right at the bottom of the “cliff.”

Our goal is simply to determine which slope our middle element resides on.

3. The Logic: Why Compare Mid vs. Right?

By comparing nums[mid] with nums[right], we can determine our relative position with 100% certainty.

• Case 1: nums[mid] > nums[right] (We are on the High Slope)
  • Intuition: “I am standing on a high value, but the destination (right end) is significantly lower.”
  • Logic: This implies that the cliff (drop)—and therefore the minimum value—must occur somewhere between my current position and the end.
  • Action: Discard the left half. Move to the right (left = mid + 1).
• Case 2: nums[mid] < nums[right] (We are on the Low Slope)
  • Intuition: “I am on a value that is smaller than the destination. The path to the end is a smooth uphill climb.”
  • Logic: This implies there is no drop to my right. The minimum value is either where I am standing or somewhere to my left.
  • Action: Discard the right half. Pull the boundary in (right = mid).

Follow-up Question

References

• https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/