Improving efficiency for two sum

I am trying to solve this problem:


Given an array of integers, find two numbers such that they add up to a specific target number.

and this is my strategy:


For each i in array num, do a binary search in numfor target - i in num.

class Solution:
    # @return a tuple, (index1, index2)

    def binary_search(self, array, target):
        def _binary_search(a, l, h, t):
            if l == h:
                return None
            elif a[(h + l) / 2] == t:
                return (h + l) / 2
            elif a[(h + l) / 2] > t:
                return _binary_search(a, l, (h + l) / 2, t)
            elif a[(h + l) / 2] < t:
                return _binary_search(a, (h + l) / 2 + 1, h, t)
            else:
                return None

        return _binary_search(array, 0, len(array) - 1, target)

    def twoSum(self, num, target):
        s_num = sorted(num)
        z_num = [(i, num.index(i)) for i in s_num]
        for tup in z_num:
            n = tup[0]
            i = tup[1]
            t = self.binary_search(s_num, target - n)
            if t != None:
                index_2 = num.index(target - n)
                if i == index_2:
                    index_2 = i + 1 + num[i:].index(target - n)
                return (i + 1, index_2 + 1)

Time complexity: \$O(n * log(n))\$

This algorithm is not accepted since the it exceeds the time limitation. How can I improve it?

You are correct that the first step is to sort the array. The second step - an actual search for solution - is also happen to be of nlog(n) complexity. What is important, they are very different nlog(n): sorting is implemented in native code, so it is virtually instantaneous comparing to the Python loops. The key to solution is to realize that the second step can be done in linear time:

Given a sorted array data you may build another sorted array target_minus_data in linear time. It is also sorted, descending. Reverse it (linear time). Now there are two sorted arrays sharing the same value. It can be found also in linear time by a merge-like algorithm.

Of course, you don't have to physically reverse target_minus_data - just iterate it backwards. If you look closely, you do not even have to build it; everything can be done in the fly. Merge data with itself, from both ends, a backward iterator returning target - data[bkwd].

StackExchange Code Review Q#57258, answer score: 8