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 [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
-~----------~----~----~----~------~----~------~--~---
