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

The idea is to use Binary Search, but here we can have equal numbers, so sometimes we need to find our minimum not in one half, but in two halves. Let us consider several possible cases of values start, mid and end.

  1. nums[start] < nums[mid] < nums[end], for example 0, 10, 20. In this case we need to search only in left half, data is not shifted.
  2. nums[mid] < nums[end] < nums[start], for example 20, 0, 10. In this case data is shifted and we need to search in left half.
  3. nums[end] < nums[start] < nums[mid], for example 10, 20, 0. In this case data is shifted and we need to search in right half.
  4. nums[end] = nums[mid], it this case we need to check the value of nums[start], and strictly speaking we not always need to search in two halves, but I check in both for simplicity of code.

Complexity: time complexity is O(log n) if there are no duplicates in nums. If there are duplicates, then complexity can be potentially O(n), for cases like 1,1,1,...,1,2,1,1,....1,1. Additional space complexity is O(1).

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

            mid = (start + end)//2
            if nums[end] <= nums[mid]:
                bin_dfs(mid + 1, end)
            if nums[end] >= nums[mid]:
                bin_dfs(start, mid)
        
        self.Min = float("inf")
        bin_dfs(0, len(nums) - 1)
        return self.Min

If you like the solution, you can upvote it on leetcode discussion section: Problem 0154