Find Minimum in Rotated Sorted Array

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

You must find the minimum element of this array in O(log n) time. You may assume no duplicates exist in the array.

What to notice first

• The array is rotated but each half (around the rotation point) is still sorted.
• The minimum is always at the rotation boundary.
• Use binary search to find the boundary: if mid < right, the minimum is in the left half (or at mid); otherwise it’s in the right half.

Examples

Input	Output	Explanation
[3,4,5,1,2]	1	Array was rotated 3 times. Minimum is at rotation point.
[4,5,6,7,0,1,2]	0	Array was rotated 4 times.
[2,1]	1	Array was rotated 1 time.
[1]	1	No rotation (or rotated n times).

Constraints

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All integers in nums are unique
• nums is sorted in ascending order and rotated between 1 and n times

Real-World Applications

Where this pattern appears

• Circular array search — finding pivot points in rotated data.
• Load balancing — detect where load distribution wraps around in circular queues.
• Time-series anomaly detection — identify rotation points in cyclic data.
• Cyclic buffer management — locate boundaries in ring buffers for memory management.

Complexity Comparison

Approach	Time	Space	Notes
Binary Search	O(log n)	O(1)	Optimal; works by comparing mid with boundaries
Iterative Scan	O(log n)	O(1)	Same complexity; alternative formulation

Approach 1: Binary Search (Recommended)

★ Recommended

Use binary search to find the rotation point. The key insight: in a rotated sorted array, one half is always sorted. If the middle element is greater than the right element, the minimum is in the right half. Otherwise, it’s in the left half (or at mid).

This avoids O(n) scanning while exploiting the sorted property.

⏱ Time O(log n) Halving search space each iteration 💾 Space O(1) Only pointers

Step-by-step Example

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

Iteration	left	right	mid	nums[mid]	nums[right]	Decision	Action
1	0	6	3	7	2	7 > 2	min in right half; left = 4
2	4	6	5	1	2	1 < 2	min in left half; right = 5
3	4	5	4	0	1	0 < 1	min in left half; right = 4
4	left == right	Return nums[4] = 0

Pseudocode

function findMin(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = (left + right) / 2
        if nums[mid] > nums[right]:
            // Rotation point is in right half
            left = mid + 1
        else:
            // Rotation point is in left half (or at mid)
            right = mid

    return nums[left]

Solution Code

Python

find_minimum_rotated_binary_search.py

from typing import List

def findMin(nums: List[int]) -> int:
    """Binary search approach: O(log n) time, O(1) space"""
    left, right = 0, len(nums) - 1

    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

C++

find_minimum_rotated_binary_search.cpp

#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

Java

FindMinimumRotatedBinarySearch.java

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

JavaScript

find_minimum_rotated_binary_search.js

function findMin(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

Rust

find_minimum_rotated_binary_search.rs

pub fn find_min(nums: Vec<i32>) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] > nums[right] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    nums[left]
}

Go

find_minimum_rotated_binary_search.go

package main

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

Approach 2: Iterative Boundary Comparison

✓ Simple

Compare the middle element with the right boundary repeatedly, shrinking the search space. This variant makes the binary search logic explicit without recursion.

⏱ Time O(log n) Halving on each iteration 💾 Space O(1) No extra structures

Pseudocode

function findMin(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right - left) / 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

Solution Code

Python

find_minimum_rotated_iterative.py

from typing import List

def findMin(nums: List[int]) -> int:
    """Iterative approach: O(log n) time, O(1) space"""
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return nums[i + 1]
    return nums[0]

C++

find_minimum_rotated_iterative.cpp

#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
    for (int i = 0; i < nums.size() - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            return nums[i + 1];
        }
    }
    return nums[0];
}

Java

FindMinimumRotatedIterative.java

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

JavaScript

find_minimum_rotated_iterative.js

function findMin(nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        if (nums[i] > nums[i + 1]) {
            return nums[i + 1];
        }
    }
    return nums[0];
}

Rust

find_minimum_rotated_iterative.rs

pub fn find_min(nums: Vec<i32>) -> i32 {
    for i in 0..nums.len() - 1 {
        if nums[i] > nums[i + 1] {
            return nums[i + 1];
        }
    }
    nums[0]
}

Go

find_minimum_rotated_iterative.go

package main

func findMin(nums []int) int {
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] > nums[i+1] {
            return nums[i+1]
        }
    }
    return nums[0]
}

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

find_minimum_in_rotated_sorted_array_space_optimized.py

"""
Solution for Find Minimum in Rotated Sorted Array
"""

def solve():
    """Implementation for approach 3 of Find Minimum in Rotated Sorted Array"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

find_minimum_in_rotated_sorted_array_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Find Minimum in Rotated Sorted Array
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

FindMinimumInRotatedSortedArraySpaceOptimized.java

/**
 * Solution for Find Minimum in Rotated Sorted Array
 * Approach 3
 */
public class FindMinimumInRotatedSortedArraySpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

find_minimum_in_rotated_sorted_array_space_optimized.js

/**
 * Solution for Find Minimum in Rotated Sorted Array
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

find_minimum_in_rotated_sorted_array_space_optimized.rs

/// Solution for Find Minimum in Rotated Sorted Array
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

find_minimum_in_rotated_sorted_array_space_optimized.go

package main

import "fmt"

// Solution for Find Minimum in Rotated Sorted Array
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Common Mistakes

Watch for these pitfalls

• Comparing with left instead of right: This can lead to incorrect decisions. Always compare nums[mid] with nums[right] to determine which half contains the minimum.
• Sorting instead of binary search: O(n log n) defeats the purpose; the problem requires O(log n).
• Assuming no rotation: If left and right are equal, the array might not be rotated; handle the base case correctly.
• Missing the exact rotation boundary: The minimum is always at the rotation point, not necessarily in a specific half.

Interview Tips

Key trade-offs to discuss

• Why compare with right? The right boundary guarantees the minimum exists in that half; left doesn’t.
• Why not compare with left? Comparing with left can lead to infinite loops or incorrect half selection.
• Follow-up with duplicates: If duplicates exist, the problem becomes harder (LeetCode 154). Discuss how duplicates break the binary search assumption.
• Rotation edge cases: No rotation (rotated n times), single rotation, all elements equal.