Python with Binary Search


  • -1
    H
    class Solution(object):
        def twoSum(self, numbers, target):
            """
            :type numbers: List[int]
            :type target: int
            :rtype: List[int]
            """
            l = len(numbers)
            for i in xrange(l):
                t = target - numbers[i]
                j = self.binSearch(numbers,t,i+1,l-1)
                if j != -1:
                    return [i+1,j+1]
            return []
    
    
        def binSearch(self,numbers,target,left,right):
            if left == right:
                if numbers[left] != target :
                    return -1
                else :
                    return left
            if left > right:
                return -1
            size = right -left +1
            min = size/2 + left
            if numbers[min] == target:
                return min
            if numbers[min] > target:
                return self.binSearch(numbers,target,left,min-1)
            else :
                return self.binSearch(numbers,target,min+1,right)
    
    

  • 0
    X

    It seems like (if i am wrong, correct me) your algorithm runs in worst case O(nlong) time, which is even worse than the conventional way (hashtable).

    And no matter what, the time complexity at least linear (because in worst case you need to loop to the second last element).


Log in to reply
 

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