The problem is:

Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

Solution:

1.Sort the elements in S using merge sort.

2.Remove the last element from S. Let y be the value of the removed element.

3.If S is nonempty, look for z= x – y in S using binary search.

4.If S contains such an element z, then STOP, since we have found y and z such that x= y+ z. Otherwise, repeat Step 2.

5.If S is empty, then no two elements in S sum to x.

Step 1 takesΘ(n lg n) time. Step 2 takes Θ(1) time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm isΘ(n lg n). The following is my implement code:

More→