Find Minimum in Rotated Sorted Array in Python and Java Using Binary Search

Problem Statement

Given a rotated sorted array nums with unique elements, return the minimum element in the array.

Input:
nums = [9, 12, 15, 2, 4, 6]

Output:
2

The smallest element in the rotated sorted array is 2.

What Is a Rotated Sorted Array?

A rotated sorted array is an array that was originally sorted in increasing order, but some elements were moved from the beginning to the end or from the end to the beginning.

Original sorted array:
[2, 4, 6, 9, 12, 15]

After rotation:
[9, 12, 15, 2, 4, 6]

In the rotated array, the minimum element is the point where the order breaks.

Simple Approach

The simple approach is to scan every element and keep track of the smallest value.

This works, but it takes O(n) time because we may need to check every number.

• Linear search solution: O(n)
• Binary search solution: O(log n)
• Space complexity: O(1)

Main Idea of Binary Search

Since the array is rotated sorted, at least one side of the array is always sorted. We can use this property to remove half of the search space each time.

We compare the middle element with the rightmost element.

If nums[mid] > nums[right]:
    minimum is on the right side

Else:
    minimum is at mid or on the left side

Important Rule

The most important comparison is between nums[mid] and nums[right].

if nums[mid] > nums[right]:
    left = mid + 1
else:
    right = mid

When the loop ends, left points to the minimum element.

Why This Works

If nums[mid] is greater than nums[right], then the smallest value must be after mid. This is because the left part contains larger rotated values.

Otherwise, nums[mid] could be the smallest value, or the smallest value could be before it. So we move right to mid.

Example 1

Input:
nums = [9, 12, 15, 2, 4, 6]

Output:
2

Explanation:
The original sorted array was [2, 4, 6, 9, 12, 15].
After rotation, it became [9, 12, 15, 2, 4, 6].

The minimum element is 2.

Example 2

Input:
nums = [30, 40, 50, 5, 10, 20]

Output:
5

Explanation:
The minimum element is 5 because it is the smallest value in the array.

Step-by-Step Dry Run

Let's dry run this input:

nums = [9, 12, 15, 2, 4, 6]

At the beginning:

left = 0
right = 5

First loop:
mid = (0 + 5) // 2 = 2

nums[mid] = 15
nums[right] = 6

15 > 6, so the minimum is on the right side.

left = mid + 1
left = 3


Second loop:
left = 3
right = 5

mid = (3 + 5) // 2 = 4

nums[mid] = 4
nums[right] = 6

4 is not greater than 6, so the minimum is at mid or on the left side.

right = mid
right = 4


Third loop:
left = 3
right = 4

mid = (3 + 4) // 2 = 3

nums[mid] = 2
nums[right] = 4

2 is not greater than 4, so the minimum is at mid or on the left side.

right = mid
right = 3


Now:
left = 3
right = 3

Loop stops.

nums[left] = 2

Final answer = 2

Watch the Video

Watch on YouTube: https://youtu.be/jPkk7zQazg4

Python Solution

This Python solution uses binary search. The unique class name is RotatedArrayMinimumFinder.

class RotatedArrayMinimumFinder:
    def find_minimum_value(self, numbers):
        left = 0
        right = len(numbers) - 1

        while left < right:
            middle = (left + right) // 2

            if numbers[middle] > numbers[right]:
                left = middle + 1
            else:
                right = middle

        return numbers[left]


# Example usage
numbers1 = [9, 12, 15, 2, 4, 6]
numbers2 = [30, 40, 50, 5, 10, 20]

finder = RotatedArrayMinimumFinder()

print(finder.find_minimum_value(numbers1))  # Output: 2
print(finder.find_minimum_value(numbers2))  # Output: 5

Java Solution

The Java solution follows the same binary search logic. The unique class name is RotatedArrayMinimumFinder.

class RotatedArrayMinimumFinder {
    public int findMinimumValue(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;

        while (left < right) {
            int middle = left + (right - left) / 2;

            if (numbers[middle] > numbers[right]) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        return numbers[left];
    }

    public static void main(String[] args) {
        int[] numbers1 = {9, 12, 15, 2, 4, 6};
        int[] numbers2 = {30, 40, 50, 5, 10, 20};

        RotatedArrayMinimumFinder finder = new RotatedArrayMinimumFinder();

        System.out.println(finder.findMinimumValue(numbers1)); // Output: 2
        System.out.println(finder.findMinimumValue(numbers2)); // Output: 5
    }
}

Code Explanation

Step 1: Create Two Pointers

We create two pointers: left at the beginning of the array and right at the end of the array.

Step 2: Find the Middle Index

In every loop, we calculate the middle index. This helps us decide which half of the array should be ignored.

middle = (left + right) // 2

Step 3: Compare Middle with Right

If the middle value is greater than the right value, the minimum value must be on the right side.

if numbers[middle] > numbers[right]:
    left = middle + 1

Step 4: Move Right Pointer

If the middle value is less than or equal to the right value, the minimum value is at middle or on the left side.

else:
    right = middle

Step 5: Return the Minimum

When the loop ends, left and right point to the same index. That index contains the minimum element.

Output for the Examples

Example 1 Output:
2

Example 2 Output:
5

Time and Space Complexity

• Time Complexity: O(log n)
• Space Complexity: O(1)

The algorithm is fast because each step removes half of the search space. It also does not use any extra array.

Key Points to Remember

• The array is sorted but rotated.
• All elements are unique in LeetCode 153.
• Compare numbers[middle] with numbers[right].
• If numbers[middle] is greater, search the right side.
• Otherwise, search the left side including middle.
• Binary search gives an optimized O(log n) solution.

Conclusion

The Find Minimum in Rotated Sorted Array problem can be solved efficiently using binary search. Instead of checking every element, we compare the middle value with the right value and remove half of the array each time.

This approach is simple, fast, and useful for many rotated sorted array problems. It works in O(log n) time and uses only O(1) extra space.