Python, binary search in a recursive form


  • 0
    S
    class Solution(object):
        def findMin(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            self.nums = nums
            return self.binary_search(0, len(nums) - 1)
                
        def binary_search(self, l, r): # binary search in recursive form
            if l == r or self.nums[l] < self.nums[r]:   # no rotation
                return self.nums[l]
            m = (l + r) // 2
            if self.nums[m] < self.nums[r]:
                return self.binary_search(l, m)
            if self.nums[m] > self.nums[r]:
                return self.binary_search(m + 1, r)
            # self.nums[m] == self.nums[r]
            # the minumum may be in [l, m] or [m + 1, r]
            return min(self.binary_search(l, m), self.binary_search(m + 1, r))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.