Find Minimum in Rotated Sorted Array (LC 153)

Pattern: Binary Search on Rotated Sorted Array
Difficulty: Medium
Key Concept: Compare mid to the right boundary: if nums[mid] > nums[right], the minimum lies in the right half; otherwise it lies in the left half (including mid).

Problem Statement

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

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

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

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

Input

• nums — rotated sorted array of distinct integers

Output

• int — the minimum value

Example

• nums = [3, 4, 5, 1, 2] → 1.

---

1. Algorithm & Pseudocode

Brute force

1. Set minVal = nums[0].
2. For each index i from 1 to n - 1:
3. If nums[i] < minVal, set minVal = nums[i].
4. Return minVal.

Optimal

1. Set left = 0, right = n - 1.
2. While left < right:
3. mid = left + (right - left) / 2.
4. If nums[mid] > nums[right], the pivot/minimum is strictly to the right of mid: set left = mid + 1.
5. Else (nums[mid] <= nums[right]), the minimum is at mid or to its left: set right = mid.
6. Return nums[left] (when the loop ends, left == right).

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why brute force works
The minimum is somewhere in the array; scanning every element finds it.

Why brute force is not enough for the constraint
Scanning is (O(n)). The problem asks for (O(\log n)), which hints at binary search.

Why binary search is possible
Before rotation, the array was sorted ascending. After rotation, there is still order: one half of the range [left, right] is “normally sorted” relative to its endpoints. Comparing nums[mid] to nums[right] tells you which side contains the drop (the minimum).

Why compare to nums[right]
If nums[mid] > nums[right], then from mid going rightward you eventually drop to the smaller elements (the old start of the original array). So the minimum cannot be in [left, mid]; it must be in [mid + 1, right].

If nums[mid] <= nums[right], the segment from mid to right is non-decreasing, so the smallest in the current window is at mid or to the left. We shrink right to mid (not mid - 1, so we do not discard the minimum at mid).

Why left = mid + 1 but right = mid
When the minimum is on the right, we know mid is not the minimum (because nums[mid] > nums[right]). When the minimum is on the left half, mid might be the minimum, so we keep it.

ASCII — “which side has the dip?”

Sorted then rotated:

   /‾‾‾‾‾\
  /       \___   ← values increase, then wrap; minimum is at the bottom of the dip

nums = [4, 5, 6, 7, 0, 1, 2]
              m     r
If nums[mid] > nums[right] → dip is to the right of mid

---

3. The Dry Run

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

Step	left	right	mid	nums[mid]	nums[right]	Action
init	0	4	—	—	2	enter loop
1	0	4	2	5	2	5 > 2 → left = 3
2	3	4	3	1	2	1 <= 2 → right = 3
end	3	3	—	—	—	stop, return nums[3] = 1

Result: 1.

---

4. Java Solution

Brute Force

class Solution {
    public int findMin(int[] nums) {
        int minVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minVal) {
                minVal = nums[i];
            }
        }
        return minVal;
    }
}

Time: (O(n)).
Space: (O(1)).

Optimal

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int 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];
    }
}

Time: (O(\log n)).
Space: (O(1)).

---

5. The “Java vs. Others” Edge

• mid = left + (right - left) / 2 avoids overflow that (left + right) / 2 can trigger with large indices.
• All distinct elements simplify the logic; variants with duplicates (LC 154) need extra handling.
• No collections needed—index arithmetic only, which is ideal for Java heap allocation (none).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	(O(n))	(O(1))	Linear scan.
Optimal	(O(\log n))	(O(1))	Halves search space using mid vs right.