CLRS Exercises 2.3-7

Problem:

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. Merge sort the elements which will take O(n log n)
2. then have two pointers one from beginning and another from end
3. if sum of both the elements a[i]+a[j] < sum then i++
4. else if sum of both the elements a[i]+a[j] > sum then j--
5. else we found print those elements a[i] and a[j].
6. complexity is O(n) in worst case.
7. Alternatively, after merge sort, do binary search for tmp=Sum - a[i] in the array a[i+1 ... n]
8. here for binary search complexity is O(log n), so still total worst case complexity is O(n log n)

Complexity: O(n log n)
Code: