Find Minimum in Rotated Sorted Array

Finding the minimum element in a rotated sorted array is a common problem in coding interviews. A rotated sorted array is one where an initially sorted array is rotated at a pivot index. The challenge is to identify the minimum element efficiently. The typical approach involves a binary search-based method that ensures an efficient search, even in large arrays.

In this article, we'll explore the rotation point, the underlying array rotation mechanism, and the steps to find the minimum element using binary search.

Problem Statement

Given a rotated sorted array, your task is to find the minimum element. The array is sorted in increasing order, and then rotated at some unknown pivot index. A simple example is:

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

In this array, the pivot index is 3, and the minimum element is 0.

Understanding Rotated Sorted Arrays

A rotated sorted array is essentially an array that was sorted in increasing order and then rotated at a particular pivot index. For example, the array [0, 1, 2, 4, 5, 6, 7] could have been rotated at the pivot index 3 to become [4, 5, 6, 7, 0, 1, 2].

In this scenario, the minimum element is the first element in the unsorted portion of the array, right after the rotation point.

Key observations:

• The smallest element is always at the pivot index or just after it.
• The sorted array ensures that once we find the rotation point, the search becomes easy.

Brute Force Approach

A simple way to solve this problem is by using a linear search. You could traverse the entire array, comparing each element with the current minimum. This would give you the correct minimum element.

However, this brute force method takes O(n) time, which is inefficient for large datasets. Instead, we will use binary search for a more optimal solution.

Optimized Approach Using Binary Search

The most efficient search for the minimum element in a rotated sorted array is by applying binary search. By leveraging the sorted array properties, we can perform a search algorithm that only takes O(log n) time complexity, rather than O(n) as in the brute force approach.

Key Steps in the Binary Search Approach:

1. Initialize two pointers, left and right, at the start and end of the array, respectively.
2. Check the middle element, and compare it with the rightmost element (which is part of the rotated sorted array).
3. If the middle element is greater than the rightmost element, the rotation point is on the right side of the middle.
4. Otherwise, the rotation point is on the left side.
5. Keep narrowing the search range by adjusting the pointers (left and right) accordingly until you find the minimum element.

Algorithm Explanation

Here’s how the binary search works:

• Iteration 1: We check the middle element and compare it with the rightmost element. If the middle element is larger, we move the left pointer to the middle plus one. If it is smaller, we move the right pointer to the middle.
• Iteration 2: We repeat the process until the search range is narrowed down to a single element, which is the minimum element.

Python Implementation

Here’s how you can implement the solution using binary search:

1
2
3
4
5
6
7
8
9
10
11
12
def findMin(nums):
    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]

Explanation of the Code:

• We initialize left and right to point to the beginning and end of the array.
• In each iteration, we calculate the mid index and compare the middle element with the rightmost element.
• If the middle element is larger than the rightmost element, the rotation point lies to the right of mid. Thus, we set left = mid + 1.
• Otherwise, the rotation point lies to the left of mid, so we set right = mid.
• The loop continues until left == right, at which point nums[left] contains the minimum element.

Time Complexity and Space Complexity

• Time Complexity: O(log n) – Due to the binary search approach, we reduce the search space by half in every iteration.
• Space Complexity: O(1) – Only a few variables (such as left, right, and mid) are used, so the space complexity is constant.

This makes the binary search approach highly efficient for large arrays.

Handling Edge Cases

1. Single Element Array

In this case, the array is trivially already rotated (or not rotated at all), and the minimum element is the only element in the array.

2. No Rotation

If the array is already sorted in ascending order (i.e., no rotation), the minimum element will be the first element.

3. Arrays with Duplicates

If the rotated sorted array contains duplicate elements, the binary search may not work as expected in certain cases. To handle this, you can modify the search to account for duplicates by reducing the right pointer.

Conclusion

Finding the minimum element in a rotated sorted array can be efficiently solved using binary search. By comparing the middle element with the rightmost element and adjusting the search range accordingly, you can identify the rotation point and minimum element in O(log n) time.

This method is optimal for large datasets and is a great example of leveraging the properties of sorted arrays combined with efficient search algorithms.