Skip to main content

Find Minimum in Rotated Sorted Array

Question​

Given an array of integers that is sorted in ascending order, but rotated at some pivot unknown to you beforehand, write a function to find the minimum element in that array.

Example 1
None

Solution​

all//Find Minimum in Rotated Sorted Array.py


def findMin(nums):
    # Edge case if array is empty or only has one element
    if len(nums) == 0:
        return None
    elif len(nums) == 1:
        return nums[0]

    left, right = 0, len(nums) - 1

    # If array is sorted, return first element
    if nums[right] > nums[0]:
        return nums[0]

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

        # If mid is greater than its left and right neighbors, it is the min
        if nums[mid] > nums[mid + 1] and nums[mid] > nums[mid - 1]:
            return nums[mid + 1]
        # If mid is less than its left neighbor, search right half
        elif nums[mid] < nums[mid - 1]:
            left = mid + 1
        # If mid is greater than its right neighbor, search left half
        else:
            right = mid - 1