Minimum in Rotated Sorted Array

Finding the minimum element in a rotated sorted array efficiently using binary search. This note corresponds to Part 6 of the Binary Search Data Structures and Algorithms (DSA) playlist in Striver's A to Z DSA course.

1. Problem Statement & The Status Quo

Given a rotated sorted array of unique integers, the objective is to find and return the minimum element in $O(\log n)$ time.

What is a Rotated Sorted Array?

• Original Sorted Array: [0, 1, 2, 4, 5, 6, 7]
• Rotated Sorted Array (Pivot at index 4): [4, 5, 6, 7, 0, 1, 2]

Array: [4, 5, 6, 7, 0, 1, 2]
Index:  0  1  2  3  4  5  6
Minimum value: 0 (located at index 4)

The Naive Brute-Force Approach

• Strategy: Iterate through the entire array sequentially (single pass) to find the minimum value.
• Time Complexity: $O(n)$
• Interview Reality: An $O(n)$ linear search is unacceptable for sorted or rotated sorted array problems. Interviewers expect an optimal $O(\log n)$ binary search solution.

2. Core Mental Model: The Rotating Pivot Property

When an array is sorted and then rotated, it loses its global sorted property, but it splits into two distinct halves when bisected at mid. Crucially, at least one half of the array will always be sorted.

Why is one half always sorted?

Because the rotation point (the pivot where the drop happens) can only reside in one of the two halves. The other half remains completely undisturbed and naturally sorted.

3. Naive vs. Better Binary Search Strategy

In standard binary search, we discard one half of the search space based on a direct comparison target. In a rotated sorted array, we cannot search for a target directly; instead, our objective is to isolate and extract the minimum value.

The Elimination Protocol:

1. Identify which half (left or right) is currently sorted.
2. Greedy Extraction: Since the identified half is sorted, its minimum element is guaranteed to be at its leftmost boundary. Grab that minimum element, compare/update our global answer, and discard that sorted half.
3. Repeat the process on the remaining half.

4. Step-by-Step Execution Walkthrough

Let's trace an example array: [4, 5, 6, 7, 0, 1, 2] with low = 0, high = 6, and answer = INT_MAX.

Iteration 1:

• low = 0 (val: 4), high = 6 (val: 2)
• mid = (0 + 6) / 2 = 3 (val: 7)
• Check Sorted Half: Is the left half sorted? array[low] <= array[mid] (4 <= 7) $\rightarrow$ Yes, Left half [4, 5, 6, 7] is sorted.
• Action:
  • The minimum in this sorted left half is at low (value 4).
  • Update answer = min(answer, array[low]) $\rightarrow$ answer = min(INF, 4) = 4.
  • Eliminate the left half by moving low past mid: low = mid + 1 (low = 4).

Iteration 2:

• low = 4 (val: 0), high = 6 (val: 2)
• mid = (4 + 6) / 2 = 5 (val: 1)
• Check Sorted Half: Is the left half sorted? array[low] <= array[mid] (0 <= 1) $\rightarrow$ Yes, Left half [0, 1] is sorted.
• Action:
  • The minimum in this sorted left half is at low (value 0).
  • Update answer = min(answer, array[low]) $\rightarrow$ answer = min(4, 0) = 0.
  • Eliminate the left half: low = mid + 1 (low = 6).

Iteration 3:

• low = 6 (val: 2), high = 6 (val: 2)
• mid = (6 + 6) / 2 = 6 (val: 2)
• Check Sorted Half: Left half [2] is trivially sorted.
• Action:
  • Update answer = min(0, 2) = 0.
  • Eliminate left half: low = 6 + 1 = 7.
• Loop terminates because low > high (7 > 6).
• Final Result: answer = 0.

5. C++ Implementation

Below is the clean, production-grade C++ implementation following the standard binary search template.

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int low = 0, high = nums.size() - 1;
        int answer = INT_MAX;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            // Optimization: If the entire search space is already sorted,
            // the minimum is simply the leftmost element.
            if (nums[low] <= nums[high]) {
                answer = std::min(answer, nums[low]);
                break;
            }

            // Check if the left half is sorted
            if (nums[low] <= nums[mid]) {
                // Pick the minimum from the sorted left half
                answer = std::min(answer, nums[low]);
                // Eliminate the left half
                low = mid + 1;
            } 
            // Otherwise, the right half must be sorted
            else {
                // Pick the minimum from the sorted right half (which starts at mid)
                answer = std::min(answer, nums[mid]);
                // Eliminate the right half
                high = mid - 1;
            }
        }
        return answer;
    }
};

6. Advanced Optimization: Early Exit on Sorted Subarrays

Notice that during binary search, we may reach a sub-segment where both the left and right halves are completely sorted (which happens when our search window falls entirely within a non-rotated portion of the array).

Note: If nums[low] <= nums[high], the entire active range [low, high] is sorted. We do not need to continue splitting and searching; we can immediately grab nums[low], update our answer, and break out of the loop.

This optimization avoids unnecessary logarithmic steps when the remaining window is already ordered.

7. Complexity Analysis

Summary and Key Takeaways

• Problem Nature: Finding the minimum in a rotated sorted array requires identifying sorted halves rather than searching for an exact target value.
• Always One Sorted Half: In any rotated sorted array split at mid, at least one half is always strictly sorted.
• Greedy Extraction: When a half is identified as sorted, its absolute minimum resides at its starting boundary (low for left, mid for right). Extract it, update the running minimum, and eliminate that half.
• Single Template Consistency: Maintain standard pointer movements (low = mid + 1 and high = mid - 1) to keep code predictable and bug-free.
• Early Break Optimization: If nums[low] <= nums[high], the active search space is fully sorted; capture nums[low] and terminate early for optimal performance.