# Difference between revisions of "TADM2E 4.8"

From Algorithm Wiki

(Recovering wiki) |
(Recovering wiki) |
||

Line 1: | Line 1: | ||

(a): | (a): | ||

− | + | <pre> | |

Sort S with any nlogn sorting method of your choice. | Sort S with any nlogn sorting method of your choice. | ||

− | for( int i = 1; i | + | for( int i = 1; i <= n; ++i ) |

{ | { | ||

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

} | } | ||

− | + | </pre> | |

(b): | (b): | ||

− | + | <pre> | |

Subtract each of S[1~n] from x to get a new array of real numbers T[1~n]. | Subtract each of S[1~n] from x to get a new array of real numbers T[1~n]. | ||

int i = 1, j = 1; | int i = 1, j = 1; | ||

− | while( i | + | while( i <=n && j <= n ) |

{ | { | ||

if( S[i] == T[j] ) | if( S[i] == T[j] ) | ||

Line 21: | Line 21: | ||

else | else | ||

{ | { | ||

− | S[i] | + | S[i] < T[j] ? ++i : ++j; |

} | } | ||

} | } | ||

− | + | </pre> | |

Another Solution to part B without creating the additional Array.. | Another Solution to part B without creating the additional Array.. | ||

− | + | <pre> | |

i = 0; | i = 0; | ||

j = n - 1; | j = n - 1; | ||

− | for (i = 0; i | + | for (i = 0; i < j; i++) |

{ | { | ||

− | while( (i | + | while( (i < j) && (S[j] + S[i] > x ) |

{ j--; | { j--; | ||

} | } | ||

Line 43: | Line 43: | ||

} | } | ||

− | + | "i" scans from left to right, "j" from right to left, | |

looking for the right pair... | looking for the right pair... | ||

− | + | </pre> |

## Revision as of 18:23, 11 September 2014

(a):

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; }

(b):

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; } }

Another Solution to part B without creating the additional Array..

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...