Solving Find Minimum in Rotated Sorted Array in Python: Step-by-Step Guide

Introduction to the Problem

The "Find Minimum in Rotated Sorted Array" problem is a classic algorithmic challenge that frequently appears in coding interviews at major tech companies. The problem statement is deceptively simple: given an array of unique integers that was originally sorted in ascending order and then rotated at some unknown pivot, find the minimum element in the array.

For example, if the original array was [0, 1, 2, 4, 5, 6, 7] and it was rotated at pivot index 3, it becomes [4, 5, 6, 7, 0, 1, 2]. The minimum element is 0. The challenge is to find this minimum efficiently, ideally in O(log n) time complexity, rather than the O(n) approach of a simple linear scan.

Why This Problem Matters

This problem is important for several reasons. First, it tests your understanding of binary search, one of the most fundamental algorithms in computer science. Second, it demonstrates your ability to adapt standard algorithms to non-standard scenarios. Third, rotated sorted arrays have practical applications in real-world systems, such as circular buffers, log files that wrap around, and scheduling systems where rotations occur naturally.

Mastering this problem also builds the foundation for solving more complex variants, such as finding a specific target in a rotated sorted array, handling duplicates, or working with rotated matrices. Interviewers use this problem because it reveals how candidates think about edge cases, loop invariants, and termination conditions.

Understanding the Structure of a Rotated Sorted Array

Before diving into the solution, it is crucial to understand the structure of a rotated sorted array. A sorted array that has been rotated has a distinctive property: it consists of two sorted subarrays concatenated together, where every element in the first subarray is greater than every element in the second subarray.

Consider the array [4, 5, 6, 7, 0, 1, 2]. The first subarray is [4, 5, 6, 7] and the second is [0, 1, 2]. The minimum element is always the first element of the second subarray, which is also the point where the rotation occurred. If the array was not rotated at all (rotation index is 0), then the minimum is simply the first element.

Key Observations

The minimum element is the only element that is smaller than its previous element.
In a rotated array, comparing the middle element with the rightmost element tells us which side is sorted and which contains the minimum.
If nums[mid] > nums[right], the minimum must be in the right half.
If nums[mid] < nums[right], the minimum must be in the left half (including mid itself).

The Binary Search Approach

The optimal solution uses a modified binary search. The key insight is that by comparing the middle element with the rightmost element, we can determine which half of the array contains the minimum. This allows us to discard half the search space with each iteration, achieving O(log n) time complexity.

Here is the logic in detail. We maintain two pointers, left and right, representing the current search boundaries. At each step, we compute the middle index and compare nums[mid] with nums[right]. If the middle element is greater than the rightmost element, it means the rotation point (and thus the minimum) lies somewhere to the right of mid, so we set left = mid + 1. Otherwise, the minimum is at mid or to its left, so we set right = mid. We continue until left equals right, at which point we have found the minimum.

Step-by-Step Implementation

Let us walk through the implementation in Python. The function takes a list of integers and returns the minimum element.

def find_min(nums):
    """
    Find the minimum element in a rotated sorted array with unique elements.
    Uses modified binary search for O(log n) time complexity.
    """
    left, right = 0, len(nums) - 1
    
    # If the array is not rotated (or has only one element),
    # the first element is the minimum.
    if nums[left] < nums[right] or len(nums) == 1:
        return nums[left]
    
    while left < right:
        mid = left + (right - left) // 2
        
        # If mid element is greater than the rightmost element,
        # the minimum is in the right half.
        if nums[mid] > nums[right]:
            left = mid + 1
        # Otherwise, the minimum is in the left half (including mid).
        else:
            right = mid
    
    # When left == right, we have found the minimum.
    return nums[left]

Let us trace through an example to understand how this works. Consider nums = [4, 5, 6, 7, 0, 1, 2].

# Initial state: left = 0, right = 6
# nums[left] = 4, nums[right] = 2
# Since nums[left] > nums[right], the array is rotated.

# Iteration 1:
# mid = 0 + (6 - 0) // 2 = 3
# nums[mid] = nums[3] = 7
# nums[mid] (7) > nums[right] (2), so minimum is in right half
# left = mid + 1 = 4

# Iteration 2:
# left = 4, right = 6
# mid = 4 + (6 - 4) // 2 = 5
# nums[mid] = nums[5] = 1
# nums[mid] (1) < nums[right] (2), so minimum is in left half (including mid)
# right = mid = 5

# Iteration 3:
# left = 4, right = 5
# mid = 4 + (5 - 4) // 2 = 4
# nums[mid] = nums[4] = 0
# nums[mid] (0) < nums[right] (1), so minimum is in left half (including mid)
# right = mid = 4

# Now left == right == 4
# Return nums[4] = 0

Handling Edge Cases

A robust solution must handle several edge cases correctly. Let us examine each one.

Single Element Array

If the array contains only one element, that element is trivially the minimum. Our implementation handles this with the initial check len(nums) == 1.

Non-Rotated Array

If the array was not rotated (rotation index is 0), the first element is the minimum. We detect this by checking if nums[left] < nums[right]. In a non-rotated sorted array, the first element is always less than the last element.

Two Element Array

With two elements, the array is either [a, b] where a < b (not rotated) or [b, a] where b > a (rotated). Both cases are handled correctly by our logic.

# Test cases for edge cases
print(find_min([1]))           # Output: 1 (single element)
print(find_min([1, 2]))        # Output: 1 (not rotated)
print(find_min([2, 1]))        # Output: 1 (rotated)
print(find_min([1, 2, 3, 4]))  # Output: 1 (not rotated)
print(find_min([3, 4, 5, 1, 2]))  # Output: 1 (rotated)

Alternative Approach: Comparing with Left Element

While comparing the middle element with the rightmost element is the most common approach, you can also compare with the leftmost element. However, this requires additional care because the comparison logic differs slightly. Here is an alternative implementation.

def find_min_alternative(nums):
    """
    Alternative approach comparing middle element with leftmost element.
    """
    left, right = 0, len(nums) - 1
    
    # Handle non-rotated case
    if nums[left] <= nums[right]:
        return nums[left]
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # Check if mid is the minimum (smaller than its previous element)
        if mid > 0 and nums[mid] < nums[mid - 1]:
            return nums[mid]
        
        # Check if mid-1 is the minimum
        if mid < len(nums) - 1 and nums[mid] > nums[mid + 1]:
            return nums[mid + 1]
        
        # Decide which half to search
        if nums[mid] > nums[left]:
            # Left half is sorted, minimum is in right half
            left = mid + 1
        else:
            # Right half is sorted, minimum is in left half
            right = mid - 1
    
    return nums[0]

This approach explicitly checks for the inflection point where the rotation occurs. While it works, the first approach comparing with the right element is generally cleaner and easier to reason about.

Handling Duplicates

A common follow-up question in interviews is: what if the array contains duplicates? The problem becomes more complex because when nums[mid] == nums[right], we cannot determine which half contains the minimum. In this case, we can only safely decrement the right pointer by one, which degrades the worst-case time complexity to O(n).

def find_min_with_duplicates(nums):
    """
    Find minimum in rotated sorted array that may contain duplicates.
    Worst-case time complexity is O(n) due to duplicate handling.
    """
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            # Minimum is in the right half
            left = mid + 1
        elif nums[mid] < nums[right]:
            # Minimum is in the left half (including mid)
            right = mid
        else:
            # nums[mid] == nums[right]
            # Cannot determine which half, so shrink from right
            right -= 1
    
    return nums[left]

# Test with duplicates
print(find_min_with_duplicates([2, 2, 2, 0, 1]))  # Output: 0
print(find_min_with_duplicates([1, 1, 1, 1, 1]))  # Output: 1
print(find_min_with_duplicates([3, 3, 1, 3, 3]))  # Output: 1

Best Practices

When implementing this solution, keep the following best practices in mind.

Use mid = left + (right - left) // 2 instead of (left + right) // 2 to avoid integer overflow in languages with fixed-size integers. While Python handles arbitrary precision integers, this is a good habit for language-agnostic thinking.
Prefer comparing with the right element over the left element, as it leads to cleaner code with fewer edge cases to handle explicitly.
Always test edge cases including single-element arrays, two-element arrays, non-rotated arrays, and fully rotated arrays (where rotation brings the array back to sorted order).
Document your assumptions clearly, especially whether the input is guaranteed to have unique elements or may contain duplicates.
Validate input in production code. While interview solutions often assume valid input, real-world code should handle empty arrays gracefully.

Adding Input Validation

def find_min_robust(nums):
    """
    Production-ready version with input validation.
    """
    if not nums:
        raise ValueError("Input array must not be empty")
    
    if len(nums) == 1:
        return nums[0]
    
    left, right = 0, len(nums) - 1
    
    # Non-rotated array
    if nums[left] < nums[right]:
        return nums[left]
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    
    return nums[left]

Complexity Analysis

Understanding the time and space complexity of your solution is essential. The binary search approach for arrays with unique elements runs in O(log n) time because we halve the search space with each iteration. The space complexity is O(1) since we only use a constant number of variables regardless of input size.

For the version that handles duplicates, the worst-case time complexity degrades to O(n). This happens when all elements are the same, and we must decrement the right pointer one step at a time. The space complexity remains O(1).

Compared to a linear scan approach, which always runs in O(n) time, the binary search approach provides significant performance benefits for large arrays with unique elements. For an array of one million elements, binary search requires approximately 20 comparisons, while a linear scan requires up to one million.

Testing Your Solution

Thorough testing is critical to ensure your solution handles all scenarios correctly. Here is a comprehensive test suite.

def test_find_min():
    # Test basic rotated arrays
    assert find_min([3, 4, 5, 1, 2]) == 1
    assert find_min([4, 5, 6, 7, 0, 1, 2]) == 0
    assert find_min([11, 13, 15, 17]) == 11
    
    # Test edge cases
    assert find_min([1]) == 1
    assert find_min([2, 1]) == 1
    assert find_min([1, 2]) == 1
    
    # Test non-rotated arrays
    assert find_min([1, 2, 3, 4, 5]) == 1
    
    # Test fully rotated (back to sorted)
    assert find_min([1, 2, 3, 4, 5]) == 1
    
    # Test rotation at different positions
    assert find_min([5, 1, 2, 3, 4]) == 1
    assert find_min([2, 3, 4, 5, 1]) == 1
    assert find_min([3, 4, 5, 1, 2]) == 1
    
    print("All tests passed!")

test_find_min()

Conclusion

The "Find Minimum in Rotated Sorted Array" problem is an excellent exercise in adapting binary search to non-trivial scenarios. By comparing the middle element with the rightmost element, we can efficiently narrow down the search space to locate the rotation point, which is where the minimum resides. The key insight is recognizing that a rotated sorted array maintains enough structure to enable binary search, even though it is not fully sorted. Whether you are preparing for coding interviews or building systems that work with circular data structures, mastering this technique will strengthen your algorithmic problem-solving skills and deepen your understanding of binary search variants. Remember to always consider edge cases, test thoroughly, and understand the complexity trade-offs when extending the solution to handle duplicates.