3
\$\begingroup\$
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
\$\endgroup\$
3
  • 4
    \$\begingroup\$ Welcome to Code Review! To help reviewers give you better answers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. See also this meta question. \$\endgroup\$ Nov 26, 2015 at 14:32
  • \$\begingroup\$ Cross posted from SO \$\endgroup\$ Nov 26, 2015 at 14:59
  • 1
    \$\begingroup\$ "Two elements" — does that mean two distinct elements? Your current code allows the same element to be chosen twice. \$\endgroup\$ Nov 26, 2015 at 21:09

3 Answers 3

5
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Your code is buggy, try running a search for a target of 10 on a list like [1, 1, 5, 1, 1]. \$\endgroup\$
    – Jaime
    Nov 26, 2015 at 20:07
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.