TADM2E 4.8

(a): <pre> Sort S with any nlogn sorting method of your choice. for( int i = 1; i <= n; ++i ) {

   int j = x - S[i];
   Binary search for j in the sub-array of S[i+1~n] and close the problem once it's been found;

} </pre> (b): <pre> Subtract each of S[1~n] from x to get a new array of real numbers T[1~n]. int i = 1, j = 1; while( i <=n && j <= n ) {

   if( S[i] == T[j] )
   {
       problem solved;
       break;
   }
   else
   {
       S[i] < T[j] ? ++i : ++j;
   }

} </pre>

Another Solution to part B without creating the additional Array.. <pre> i = 0; j = n - 1;

for (i = 0; i < j; i++) {

 while( (i < j) && (S[j] + S[i] > x )
 { j--;
 }
 if (x == (S[j] + S[i])
 {
   return (S[i],S[j]);
   break;
 }

}

"i" scans from left to right, "j" from right to left, looking for the right pair... </pre>

Navigation menu