Find Minimum in Rotated Sorted Array - Python Solution

1. Introduction

The "Find Minimum in Rotated Sorted Array" problem is an intriguing twist on binary search. It involves finding the minimum element in an array that has been sorted and then rotated. This problem tests the ability to adapt binary search to a modified array structure, requiring a solution with O(log n) runtime complexity.

Problem

Suppose an array of length n, sorted in ascending order, is rotated between 1 and n times. Given this sorted and rotated array nums with unique elements, the task is to find and return the minimum element of this array. The algorithm should run in O(log n) time.

2. Solution Steps

1. Implement a modified binary search to find the point of rotation (the smallest element).

2. Compare the middle element with the end element to determine which half of the array is sorted.

3. If the middle element is greater than the end element, the minimum is in the right half; otherwise, it's in the left half.

4. Continue the search in the identified half.

5. The point where the order changes is where the minimum element is located.

3. Code Program

def findMin(nums):
    if not nums:
        return None

    start, end = 0, len(nums) - 1

    while start < end:
        mid = (start + end) // 2

        # Check if the middle element is greater than the end element
        if nums[mid] > nums[end]:
            start = mid + 1  # The minimum is in the right half
        else:
            end = mid  # The minimum is in the left half

    return nums[start]

# Testing the function with examples
print(findMin([4, 5, 6, 7, 0, 1, 2]))
print(findMin([0, 1, 2, 4, 5, 6, 7]))

Output:

0
0

Explanation:

1. Binary Search Application: The algorithm uses a binary search but modifies it to find the minimum element in a rotated array.

2. Mid-Element Comparison: In each iteration, it compares the middle element with the end element to decide which half is sorted.

3. Search Space Reduction: Depending on whether the middle element is greater or smaller than the end element, the search space is reduced.

4. Finding the Minimum: The minimum element is found at the point where the order of the sorted array changes.

5. Return Value: The function returns the minimum element in the rotated sorted array.