>>>For those who know about asymptotic behavior:
>>>
>>>
Given an array of increasing numbers and a number X, create a linear algorithm that finds whether the array contains two numbers that sum to X (and those two numbers if they exist).>>>
>>>Daniel
>>
>>This should work (I think)
>>
>>for i = 1 to alen(myarray)
>> for j = 1 to alen(myarray)
>> if myarray(i)+myarray(j) = X
>> return i,j
>> endi
>> next j
>>next i
>
>It should work, but it may be slow executing. The array is stated to be sorted, so you are supposed to take advantage of that fact - and that is what I see as the tricky part.
>
>Hilmar.
You are correct. This would help speed it up some:
for i = 1 to alen(myarray)
for j = 1 to alen(myarray)
if myarray(i)+myarray(j) = X
return i,j
endi
if myarray(i)+myarray(j) > X
exit
endi
next j
next i
This makes me think of something my Professor told me: "Never use double for loops unless you have to" (I am not sure if I have to but he doesn't have to know <bg>)
Einar
Semper ubi sub ubi.