a problem with an algorithm

[Sophia]

Hi guys,

I've tried to understand the following problem but I have some difficulties in understanding it's solution,here is the problem:

describe a theta(nlgn)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exists two elements in S whose some is exactly x.

Here is the solution:


Algorithm 4 CHECKSUMS(A; x)
Input: An array A and a value x.
Output: A boolean value indicating if there is two elements in A whose sum is x.
A SORT(A)
n length[A]
for i to n do
if A[i] > 0 and BINARY-SEARCH(A;A[i] - x; 1; n) then
return true
end if
end for
return false


I understand the overall algorithm but my problem is that why should we search for 'A[i] - x' because the sum of 'A[i] - x' and 'x' is A[i]. Maybe I don't understand the problem well, would you please help me with this algorithm.

Thanks in advance.
Sophia

[ma...@smartfills.com]

среда, 25 апреля 2012 г., 8:02:52 UTC+12 пользователь Sophia написал:

BS. It cannot work. What happens, if all elements of A negative? You'll get false and no matter what value of x is. If must be replaced: If A[i]>x, of course. Then you must look for x-A[i], not for A[i]-x.

[Nobody]

On Tue, 24 Apr 2012 13:02:52 -0700, Sophia wrote:

> I understand the overall algorithm but my problem is that why should we
> search for 'A[i] - x' because the sum of 'A[i] - x' and 'x' is A[i].

You should be searching for x-A[i], as the sum of A[i] and x-A[i] is x.

Searching for A[i]-x would make sense if you were searching for two
elements whose *difference* is x.

[ma...@smartfills.com]

четверг, 26 апреля 2012 г., 2:17:17 UTC+12 пользователь Nobody написал:

That's just what I said. But I was incorrect too. Proper condition must be not "If A[i]>0" nor "If A[i]>x". It must be "If A[i]>x/2" . I can add that this algorithm is not the optimal. There is a way to bypass binary search.