Returns two elements from a list whose sum is a target variable

Question

def search(a,b):
    for d in b:
        if a==d:
            m=True
            break
        else:
            m=False
    return m

x=[1,4,5,7,9,6,2]
target=int(raw_input("Enter the number:"))
for i in x:
    if i<target:
        pair=int(target)-int(i)
        in2=search(pair,x)
        if in2==True:
            print "the first number= %d the second number %d"%(i,pair)
            break

Answer 1

Your search function is terribly unclear. search is a vague name, and a, b, d and m don't communicate anything. Looking at the usage I can see you're testing if a number is in the list, but Python can already do that for you much more readably.

if number in list

The in keyword tests if a value exists in a list, returning either True or False. So you can forget about search and just directly test for pair's existence in the main loop:

x = [1,4,5,7,9,6,2]
target = int(raw_input("Enter the number:"))
for i in x:
    if i < target:
        pair = int(target) - int(i)
        if pair in x:
            print "the first number= %d the second number %d"%(i,pair)
            break

Back to the naming, x is not clear, at least using numbers indicates what it contains. x implies a single value which makes using for i in x extra confusing. pair also sounds like it's multiple items, when really it's the difference you want.

You also don't need to call int on i when the list is populated with integers already.

Lastly, you're using the old form of string formatting. You should instead use str.format, like so:

            print("the first number= {} the second number {}".format(i,pair))

It works very similarly, except that it's type agnostic. It will just do it's best to get a string representation of the two values and insert them. There's lots of other uses for this approach so it's good to get used to.

Answer 2

Your algorithm is \$O(n^2)\$, as you are scanning the full list for every item of the list.

A more efficient algorithm can be put together by first sorting the list:

def find_pair_adding_to_target(target, values):
    sorted_values = list(sorted(values))
    lo_index = 0
    hi_index = len(values) - 1
    while lo_index < hi_index:
        pair_sum = sorted_values [lo_index] + sorted_values [hi_index]
        if pair_sum < target:
            lo_index += 1
        elif pair_sum > target:
            hi_index -= 1
        else:
            return sorted_values [lo_index], sorted_values [hi_index]
    raise ValueError('No pair adds to {}'.format(target))

The algorithm searching for the pair in the sorted list is \$O(n)\$, but the sorting is \$O(n \log n)\$, which dominates and is also the complexity of the full algorithm.

Answer 3

Just so you know, you can return from within a loop:

def search(a,b):
    for d in b:
        if a==d:
            return True
    return False

Which is equivalent to what SuperBiasedMan suggested. Note that this test is O(n) which is not optimal. If you move the numbers to a dictionary, you can test that in O(1).

contains = a in somelist  # O(n)
contains = a in somedict  # O(1)

Since performance is tagged, I suggest using a set (or dict) to test if a matching component exists on the list. The issue with this approach is that matches must not be distinct.

numbers = [1,4,5,7,9,6,2]
numberset = set(numbers)
target = int(raw_input("Enter the number:"))
for x in numbers:
    if target-x in numberset:
        print "Found non-distinct components: {0} and {1}".format(x, target-x)

Second revision does find distinct pairs, but is more complicated. Take your time going through it. The dictionary creates inverse mapping from elements back to indexes from which they came. Also pairs (i,j) and (j,i) are equivalent, so only one of the two is taken.

def test(numbers, target):
    indexes = {}
    for i,x in enumerate(numbers):
        indexes[x] = indexes.get(x,[])+[i]
    print indexes

    for i,x in enumerate(numbers):
        for j in indexes.get(target-x,[]):
            if i < j:
                print "Found distinct components: {0} + {1} = {2} "\
                "at positions {3} and {4}".format(x, target-x, target, i, j)
    print "End of results."

Example output:

test([1,4,5,7,9,6,2,1,5], 10)

{1: [0, 7], 2: [6], 4: [1], 5: [2, 8], 6: [5], 7: [3], 9: [4]}
Found distinct components: 1 + 9 = 10 at positions 0 and 4
Found distinct components: 4 + 6 = 10 at positions 1 and 5
Found distinct components: 5 + 5 = 10 at positions 2 and 8
Found distinct components: 9 + 1 = 10 at positions 4 and 7
End of results.