Find Minimum In Rotated Sorted Array Leetcode In Python

Problem Link

class Solution:
    def findMin(self, nums: List[int]) -> int:
        low, high = 0, len(nums) - 1

        while low < high:
            mid = low + (high - low) // 2

            if nums[mid] > nums[high]:
                low = mid + 1
            else:
                high = mid

        return nums[low]

Explanation:

This algorithm works as follows:

• In each step, it checks the middle element (mid).
• If nums[mid] is greater than nums[high], it means the minimum element is on the right side, so we update low = mid + 1.
• If nums[mid] is less than or equal to nums[high], it means the minimum element is on the left side or at mid, so we update high = mid.
• The loop continues until low and high point to the same element, which is the minimum element.

This approach ensures O(log n) time complexity as we eliminate half of the search space in each iteration.

Find Minimum In Rotated Sorted Array Leetcode In Python