Leetcode 153: Find Minimum in Rotated Sorted Array

The original question can be found here.

The question is asking us to find the minimum element in a rotated sorted array. After analysing, we can observe the following:

The array can be divided into 2 parts. The left part is asending, and right part is also asending, but left subarry is greater than right subarray.

Brute Force

The first solution we can think of is scanning through the array and find the first element that is smaller than left neighbor. This solution is simple but the time complexity is O(n), which does not meet the problem’s requirement.

Binary Search

Since the question is explictly asking us for a O(logn) solution, we need to use binary search. But how? Once we find the middle element, what shall we compare it to?

There’re 2 cases. First case:

If nums[middle] > nums[end], we know we need to go to right part. Second case:

If nums[middle] < nums[end], we know we need to go to left part.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        end = len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] > nums[end]:
                left = mid
            else:
                right = mid
        return min(nums[left], nums[right])

Time complexity: O(logn). Space complexity: O(1).

So why we compare with the end element, not the start element? More explictly, if nums[middle] > nums[start], we go to right part, otherwise left part? Consider this case:

[1, 2, 3, 4, 5, 6]
       ^
       m

If the array is acutually not rotated at all, if we stick with nums[middle] > nums[start] and we go to right part, we’ll miss the right answer.