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
-
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\$– SuperBiasedManNov 26, 2015 at 14:32
-
\$\begingroup\$ Cross posted from SO \$\endgroup\$– SuperBiasedManNov 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\$– 200_successNov 26, 2015 at 21:09
3 Answers
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.
-
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\$– JaimeNov 26, 2015 at 20:07
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.
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.