Just scan the array from both sides in natural order, and it requires
at most n times of summation, and n times of comparison.
e.g.
to find 7 + 9 = 16
1 3 7 9 16 28 49
1+49 > 16 -> 1+28 .. .-> 1+16 -> 1+9 < 16 then
3 + 9 < 16 -> 3 + 16 > 16 then
7 + 16 > 16 -> 7 + 9 find it.
ravi 写道：
> The input is an array S containing n real numbers, and a real number
> x, Design an algorithm to determine whether there are 2 elements of S
> whose sum is exactly x. and onemore thing is that S is in sorted
> order.
>
> I got the solution with the complexity of O(n logn) but I am searching
> for an algo. on O(n) complexity.
>
> My solution is like this,
>
> for each element k in S // There are n element so iterates n
> times
> {
> k = k - x;
> if( BinarySearch(k,S) ) // complexity is O ( log n )
> {
> found an elemnt
> break;
> }
> }
>
> So overall complexity is O ( n logn).
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
