Two sum with two lists

Suppose we have two sorted lists, and we want to find one element from the first, and the other element from the 2nd list, where the sum of the two elements equal to a given target. If there are multiple combinations, need to find all the combinations.

Any bugs, performance improvement ideas in terms of algorithm time complexity or code style advice is highly appreciated. My basic idea is to scan the first list from the beginning, and scan the second list from the end, a similar approach to how we resolve the 2-sum classic problem in one list.

def two_sum(list1, list2, target, result):
    i = 0
    j = len(list2) - 1
    while i = 0:
        if list1[i] + list2[j] == target:
            result.append((list1[i], list2[j]))
            i += 1
            j -= 1
            while i = 0 and list2[j] == list2[j+1]:
                j -= 1
        elif list1[i] + list2[j] > target:
            j -= 1
        else:
            i += 1
if __name__ == "__main__":
    list1 = [1,3,5,7]
    list2 = [2,3,4,5]
    result = []
    two_sum(list1, list2, 6, result)
    print result

Assuming that your lists are sorted and this is something that comes out of problem description and the part where you need to find something in 99% of that kind of questions you want to use binary search. So basically all your code could be written like this:

from bisect import bisect_left

def binary_search(a, x):
    pos = bisect_left(a, x)
    return pos if pos != len(a) and a[pos] == x else -1

def two_sum(a, b, target):
    result = []
    for num in a:
        index = binary_search(b, target-num)
        if index != -1:
            result.append((num, b[index]))
    return result

Now if you want to save some memory, you might want to make two_sum a generator, which will make it look like this:

def two_sum(a, b, target):
    result = []
    for num in a:
        index = binary_search(b, target-num)
        if index != -1:
            yield num, b[index]

I cannot really call my answer a review to your code because I completely overwrote a solution for this. But as I mentioned in the beginning whenever a problem says something about sorted lists and searching on it, most likely you will use bsearch in your solution.

StackExchange Code Review Q#153090, answer score: 4