Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. Tags: Array

Try It!

Discussion

Video

Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo = 0
        hi = len(nums) - 1
        
        while lo < hi:
            mid = lo + (hi - lo) // 2
            # important to do mid, hi comparison so we converge down to min instead of highest lo num
            if nums[mid] < nums[hi]:
                hi = mid
            else:
                lo = mid + 1

        return nums[lo]