Divide and conquer, recursive approach


  • 0
    D
    1. Cut the array into half
    2. Perform search in both subarrays, until we find the target
    class Solution(object):
    
        def __init__(self):
            self.res = -1
        
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            l, r = 0, len(nums) - 1
            self.helper(nums, target, l, r)
            return self.res
    
        def helper(self, nums, target, l, r):
            if l == r:
                if nums[l] == target :
                    self.res = l
                return
            mid = l + (r - l) / 2
            self.helper(nums, target, l, mid)
            self.helper(nums, target, mid + 1, r)
    

Log in to reply
 

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