Recursive Log(N) Solution


  • 0
    U
    class Solution(object):
        def search(self, nums, target, low=None, high=None):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if low > high:
                return - 1
                
            if low is None:
                low = 0
                high = len(nums) - 1
    
            middle = (low + high)/2
    
            if nums[middle] == target:
                return middle
            elif low != high:
                if nums[middle] <= nums[high]:
                    if nums[middle] < target <= nums[high]:
                        return self.search(nums, target, middle + 1, high)
                    else:
                        return self.search(nums, target, low, middle - 1)
                else:
                    if nums[low] <= target < nums[middle]:
                        return self.search(nums, target, low, middle - 1)
                    else:
                        return self.search(nums, target, middle + 1, high)
            
            return -1
    

Log in to reply
 

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