Find Minimum in Rotated Sorted Array in DSA C++

Mental Model

A rotated sorted array is like a sorted list that has been shifted. The smallest element is the point where the shift happened.

Analogy: Imagine a clock face with numbers 1 to 12 in order. If you rotate the clock so that 3 is at the top, the smallest number is where the rotation starts, like the new '12'.

Original sorted array:
1 -> 2 -> 3 -> 4 -> 5 -> null
Rotated array:
4 -> 5 -> 1 -> 2 -> 3 -> null
          ↑ smallest element

Dry Run Walkthrough

Input: array: [4, 5, 1, 2, 3]

Goal: Find the smallest number in the rotated sorted array

Step 1: Set left=0, right=4 (start and end indices)

[4, 5, 1, 2, 3], left=0, right=4

Why: We start searching the whole array

Step 2: Calculate mid = (0+4)//2 = 2, check value at mid=1

[4, 5, 1, 2, 3], mid=2 (value=1)

Why: Mid helps us decide which half contains the smallest element

Step 3: Compare mid value (1) with right value (3), since 1 < 3, move right to mid

[4, 5, 1, 2, 3], left=0, right=2

Why: Minimum must be in left half including mid

Step 4: Calculate mid = (0+2)//2 = 1, check value at mid=5

[4, 5, 1, 2, 3], mid=1 (value=5)

Why: Check mid again to narrow search

Step 5: Compare mid value (5) with right value (1), since 5 > 1, move left to mid+1

[4, 5, 1, 2, 3], left=2, right=2

Why: Minimum must be in right half excluding mid

Step 6: Left equals right, found minimum at index 2 with value 1

[4, 5, 1, 2, 3], left=2, right=2 (value=1)

Why: Search narrowed to one element which is minimum

Result:

Minimum element is 1 at index 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int findMin(const vector<int>& nums) {
    int left = 0;
    int right = (int)nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;  // find middle index
        if (nums[mid] > nums[right]) {
            left = mid + 1;  // minimum is in right half
        } else {
            right = mid;  // minimum is in left half including mid
        }
    }
    return nums[left];  // left == right is minimum
}

int main() {
    vector<int> nums = {4, 5, 1, 2, 3};
    cout << findMin(nums) << endl;
    return 0;
}

int mid = left + (right - left) / 2; // find middle index

Calculate middle index to split search space

if (nums[mid] > nums[right]) {

Check if minimum is in right half by comparing mid and right values

left = mid + 1; // minimum is in right half

Move left pointer to mid+1 to discard left half

right = mid; // minimum is in left half including mid

Move right pointer to mid to keep left half including mid

return nums[left]; // left == right is minimum

Return the minimum element found when pointers meet

Output

1

Complexity Analysis

Time: O(log n) because the search space halves each step using binary search

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to scanning all elements O(n), this binary search method is much faster for large arrays

Edge Cases

Array not rotated (e.g., [1, 2, 3, 4, 5])

Minimum is the first element, code returns it correctly

DSA C++

while (left < right) {

Array with one element (e.g., [10])

Returns the single element as minimum

DSA C++

while (left < right) {

Array rotated at last element (e.g., [2, 3, 4, 5, 1])

Correctly finds minimum at last index

DSA C++

if (nums[mid] > nums[right]) {

When to Use This Pattern

When you see a sorted array that might be rotated and need to find the smallest element quickly, use binary search to find the rotation point.

Common Mistakes

Mistake: Comparing mid value with left instead of right pointer value
Fix: Always compare nums[mid] with nums[right] to decide which half to search

Mistake: Using while (left <= right) instead of while (left < right), causing infinite loop
Fix: Use while (left < right) to ensure pointers converge correctly

Summary

Finds the smallest element in a rotated sorted array using binary search.

Use when you have a sorted array shifted at some pivot and want to find the minimum efficiently.

The smallest element is the only point where the order breaks, found by comparing mid and right values.