[Introduction to Algorithms, CLRS] Exercises 2.3-7

This is a solution for Introduction to Algorithms. I write this for my study purpose.

Exercises 2.3-7

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

Answer:

To make the answer a Θ(n lg n)-time algorithm, we need to sort the set S, otherwise, we cannot achieve Θ(n lg n). If we just do brute-force approach (select an integer i, and find x-i), we can solve this problem at Θ(n^2) at best. 

If we sort the set in Θ(n lg n) and select an integer i, we can find x-i at Θ(lg n) by binary search for each every integer, which result in Θ(n lg n) for entire search.

There is a faster algorithm. Suppose we have two pointers for the array, one at the beginning (pointer 1) and the other at the end (pointer 2). We check the sum of the two values in the array and if the sum is larger than the x, then we move pointer 2 to the left and if the sum is smaller than x, we move the pointer 1 to the right. If we cannot find the answer until the two pointers crossed, there is no answer.

1    i <-1, j <- n

2    while i <= j do

3        if S[i] + S[j] = x then

4            return true

5        if S[i] + S[j] < x then

6            i <- i + 1

7        else

8            j <- j - 1

9    return false

Note: The solution above allows i and j to have the same value.

source: https://www.cs.helsinki.fi/webfm_send/1444