Bruce Yang has the right O(n)N algorithm. Basically it is:
1. Have two pointers ptr1 = arr[0] and ptr2 = arr[ n - 1].
2. While (!found && ptr1 < ptr2)
a. sum = ptr1 + ptr2
b. if (sum == req_sum)
found the numbers .. ptr1 and ptr2
c. if (sum < req_sum)
Increment ptr1
d. if (sum > req_sum)
Decrement ptr2
-Dhyanesh
On 8/7/06, Lego Haryanto <[EMAIL PROTECTED]> wrote:
>
> I'm not sure if we can find an O(n) algorithm for this, but there is an
> improvement to your O(n lg n) algorithm, which basically limits your binary
> search scope each time we scan each number.
>
> For instance, in the set of 1, 3, 7, 9, 16, 28, 49 and x=16, ... we start
> with a scope of the whole S except for the first one [3,7,9,16,28,49]
> subject to binary search.
>
> When we see the first number (1), we know for sure we're looking for 15
> (which is 16-1), so when we binary search and we can't find 15, we should
> narrow down the search scope to the upper limit of 9 for the next number
> (there is no reason to include 16, 28, and 49 for the next search since the
> next number we scan will definitely be greater than 1). So, we set 9 as our
> upper limit.
>
> When the next number (3) comes, we don't even need to binary search because
> our search range is only [7, 9], and 13 is definitely out of range.
>
> Note that the lower limit for the binary search set can always be set to the
> next-neighbor of the number being evaluated.
>
> Eventually, the algorithm will find the desired pair, or the algorithm
> terminates because lower-limit is greater than upper-limit, which means
> there's no such pair.
>
> Please confirm.
>
>
> On 8/7/06, ravi <[EMAIL PROTECTED]> wrote:
> >
> > 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).
> >
> >
> >
> >
> >
>
>
>
> --
> Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
