Find Minimum in Rotated Sorted Array

Problem Statement

You are given a sorted array of unique integers that has been rotated between 1 and n times. Find the minimum element. You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: Original sorted array [1,2,3,4,5] was rotated 3 times.

Example 2:

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

Example 3:

Input: nums = [11, 13, 15, 17]
Output: 11
Explanation: Not actually rotated (or rotated n times).

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All values are unique.

Difficulty: Medium (LC 153)

---

Pattern Recognition

• What is the input structure? A sorted array that has been rotated — creating two sorted halves.
• What are we optimizing? Finding the minimum in O(log n) time.
• What pattern does this fit? Modified Binary Search. The array has a "pivot" where the rotation happened. One half is always sorted, and you can determine which half contains the minimum by comparing mid to the boundaries.
• Why does this pattern fit? A rotated sorted array has the property that one half (left or right of mid) is always sorted. By comparing nums[mid] with nums[right], you can determine which half contains the pivot (minimum). This eliminates half the search space each iteration — exactly binary search.

---

Approach

Brute Force — Linear Scan

Scan the array for the minimum.

return min(nums)

Time: O(n). Space: O(1). Why insufficient: The problem explicitly requires O(log n). The interviewer wants binary search.

Optimal — Binary Search

Key Insight: Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum is in the right half (the rotation point is there). If nums[mid] <= nums[right], the minimum is in the left half (including mid). This narrows the search by half each time.

Step-by-step:

1. Initialize lo = 0, hi = n - 1.
2. While lo < hi:
   • Compute mid = (lo + hi) // 2.
   • If nums[mid] > nums[hi]: the pivot (minimum) is to the right of mid. Set lo = mid + 1.
   • Else: the minimum is at mid or to its left. Set hi = mid.
3. Return nums[lo].

function findMin(nums):
    lo, hi = 0, n - 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).

Why compare with nums[hi] (right) and not nums[lo] (left)? Comparing with nums[lo] is ambiguous. Consider [3, 4, 5, 1, 2]: nums[mid] = 5, nums[lo] = 3. nums[mid] > nums[lo] is true, but the minimum is to the right. However, in [1, 2, 3, 4, 5]: nums[mid] = 3, nums[lo] = 1. Same condition nums[mid] > nums[lo] is true, but the minimum is to the left. The comparison with nums[hi] always works because:

• nums[mid] > nums[hi] guarantees the rotation point is in (mid, hi].
• nums[mid] <= nums[hi] guarantees mid to hi is sorted, so minimum is in [lo, mid].

---

Walkthrough

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

Iteration	lo	hi	mid	nums[mid]	nums[hi]	Comparison	Action
1	0	6	3	7	2	7 > 2 → min is right	lo = 4
2	4	6	5	1	2	1 <= 2 → min is left (incl mid)	hi = 5
3	4	5	4	0	1	0 <= 1 → min is left (incl mid)	hi = 4
4	lo == hi = 4	—	—	—	—	Loop ends	—

Answer: nums[4] = 0

Second example — no rotation: nums = [1, 2, 3, 4, 5]

Iteration	lo	hi	mid	nums[mid]	nums[hi]	Action
1	0	4	2	3	5	3 <= 5 → hi = 2
2	0	2	1	2	3	2 <= 3 → hi = 1
3	0	1	0	1	2	1 <= 2 → hi = 0
4	lo == hi = 0	—	—	—	—	Loop ends

Answer: nums[0] = 1 — correctly identifies the first element as minimum.

---

Implementation

TypeScript

function findMin(nums: number[]): number {
    let lo = 0, hi = nums.length - 1;

    while (lo < hi) {
        const mid = (lo + hi) >> 1;

        if (nums[mid] > nums[hi]) {
            // Minimum is in the right half (rotation point is there)
            lo = mid + 1;
        } else {
            // Minimum is at mid or in the left half
            hi = mid;
        }
    }

    return nums[lo];
}

C++

int findMin(vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;

    while (lo < hi) {
        int mid = (lo + hi) / 2;

        if (nums[mid] > nums[hi]) {
            // Minimum is in the right half (rotation point is there)
            lo = mid + 1;
        } else {
            // Minimum is at mid or in the left half
            hi = mid;
        }
    }

    return nums[lo];
}

Watch out:

1. Using lo <= hi instead of lo < hi. With lo <= hi, you need an extra check to avoid infinite loops. The lo < hi condition naturally terminates when lo == hi, which is the answer.
2. Setting hi = mid - 1 instead of hi = mid. When nums[mid] <= nums[hi], mid itself could be the minimum. Setting hi = mid - 1 would skip it. Always use hi = mid in the else branch.
3. Comparing with nums[lo] instead of nums[hi]. As explained above, comparing with the left boundary is ambiguous for non-rotated arrays. Always compare with the right boundary.

---

Complexity Analysis

	Time	Space
Linear Scan	O(n)	O(1)
Binary Search	O(log n)	O(1)

Bottleneck: Each iteration eliminates half the remaining elements. After log n iterations, only one element remains. No extra space is needed — just two pointers.

---

Edge Cases

1. Array is not rotated (sorted) — Minimum is nums[0]. The algorithm correctly converges to index 0 since nums[mid] <= nums[hi] always holds.
2. Array rotated once ([5, 1, 2, 3, 4]) — Minimum is at index 1. The algorithm finds it in log n steps.
3. Two elements ([2, 1]) — mid = 0, nums[0] > nums[1], so lo = 1. Return nums[1] = 1.
4. Single element — lo == hi immediately, return nums[0].
5. Minimum at the very end — e.g., [2, 3, 4, 5, 1]. The binary search correctly follows the right branch.
6. All elements identical — Not applicable (problem says unique), but for LC 154 (with duplicates), the worst case degrades to O(n).

---

Related Problems

• LC 154 — Find Minimum in Rotated Sorted Array II — Same problem but with duplicates. When nums[mid] == nums[hi], you cannot decide which half, so do hi -= 1. Worst case O(n).
• LC 33 — Search in Rotated Sorted Array — Search for a target. Uses the same "which half is sorted" logic, plus a target comparison.
• LC 81 — Search in Rotated Sorted Array II — Search with duplicates. Combines LC 33 and LC 154 ideas.
• LC 162 — Find Peak Element — Binary search on a different invariant (comparison with neighbors).

---

What is Expected at Each Level

Junior: Recognize that the array is sorted but rotated. Attempt binary search but may get confused about which boundary to compare. May use nums[lo] comparison and get stuck on edge cases.

Mid-level: Correctly compare nums[mid] with nums[hi]. Write the solution without bugs. Explain why hi = mid (not mid - 1). Handle the non-rotated case. Discuss LC 154 (duplicates variant) as a follow-up.

Senior: Write the solution in under 3 minutes. Prove correctness of the invariant: at every step, the minimum is in [lo, hi]. Extend to searching for a target (LC 33). Discuss the duplicates variant and prove the O(n) worst case. Connect to the general "binary search on a non-monotonic function" framework.