# Python with Binary Search

• ``````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)

``````

• 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).

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