Dec 18, 2008

Given sorted array of numbers, find two numbers in array with difference equal to k (in-place) Can we do better than nlogn?

Given sorted array of numbers, find two numbers in array with difference equal to k (in-place) Can we do better than nlogn?


int left, right, diff;
for (left = 0, right = 1; right < size; right++)
{
while ( 1 )
{
diff = array[right] - array[left];
if ( diff == target ) // return output
if ( diff < target ) break;
left++;
}
}
// return not found


the complexity is O(n).
Note the difference with two numbers sum up to k

No comments:

Post a Comment