Find Minimum in a Rotated Sorted Array

Problem Summary

• Given a rotated sorted array, find the minimum element in $O(logn)$

Similar Problem

What is Being Asked?

• Do binary search and find the minimum element

Why This Works

• Always, there is at least one side of the array that is in the sorted order
• Once we find whether it is left or right side then we can determine the lowest seen so far and then search the other side

Main Concepts Used

• Binary Search

Time & Space Complexity

• Time: $O(logn)$ → Reason: Binary searching
• Space: $O(1)$ → Reason: Just using pointers

Code

class Solution:
    def findMin(self, nums: List[int]) -> int:
        minSoFar = nums[0]
        l, r = 0, len(nums) - 1
        while l <= r:
            m = (l + r) // 2
            mid = nums[m]
            leftMost = nums[l]
            rightMost = nums[r]

            if mid <= rightMost: # right side is sorted
                minSoFar = min(minSoFar, mid)
                r = m - 1
            else:
                minSoFar = min(minSoFar, leftMost)
                l = m + 1

        return minSoFar

Common Mistakes / Things I Got Stuck On

• Trying to figure out whether a number is minimum by using nums[m-1 % len(nums)] -> this was not needed after all