Leetcode 0153. Find Minimum in Rotated Sorted Array

Problem statement

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Solution

In fact this problem is very similar to problem 0033, but here we need to find not target element, but minimum. We can use exactly the same logic:

1. if nums[end] < nums[mid], this means that minimum we are looking for is situated in the right half.
2. elif nums[end] > nums[mid] means that minimum we are looking for is situated in the left half.
3. if end - start <= 1 means that we have interval of length 1 or 2, so we can directly check minimum.

Also here I did it in recursive, not iterative way just for the purpose of exercise.

Complexity

It is O(log n) for time and space.

Code

class Solution:    
    def findMin(self, nums):
        def dfs(start, end):
            if end - start <=  1:
                return min(nums[start], nums[end])

            mid = (start + end)//2
            if nums[end] < nums[mid]:
                return dfs(mid + 1, end)
            elif nums[end] > nums[mid]:
                return dfs(start, mid)

        return dfs(0, len(nums) - 1)