CLRS Solutions | Exercise 2.3-7

Describe a $\Theta(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$.

If the running time constraint was not there, we might have intuitively used the brute-force method of picking one element at a time and iterating over the set to check if there exists another element in the set such that sum of them is $x$. Even in average case, this brute-force algorithm will run at $\Theta(n^2)$ time (as we have to iterate over the set for each element).

But we have to think of a $\Theta(n \lg n)$-time algorithm.

So, the problem asks for a search algorithm and we already know binary search is an efficient one at that which runs at $\Theta(\lg n)$ time for a sorted array (see Exercise 2.3-5).

So, we can sort the array with merge sort ($\Theta(n \lg n)$) and then for each element $S[i]$ in the array, we can do a binary search for $x - S[i]$ on the sorted array ($\Theta(n \lg n)$). So, the overall algorithm will run at $\Theta(n \lg n)$ time.

$$\textsc {Sum-Search }(S, x)$$$$\begin{aligned}1& \quad \textsc {Merge-Sort}(S,\,1,\,S.length) \\2& \quad \textbf {for }i=1\textbf { to }S.length \\3& \quad \qquad index=\textsc {Binary-Search}(S,\,x-S[i]) \\4& \quad \qquad \textbf {if }index\not=\text { NIL }\text { and }index\not=i \\5& \quad \qquad \qquad \textbf {return }true \\6& \quad \textbf {return }false \\\end{aligned}$$

Note the additional conditional check for $index$ not being equal to $i$ in line 4. This is necessary for avoiding cases where the expected sum, $x$, is twice of any element. An algorithm without this conditional check, will wrongly return true in such cases. This was pointed out by Ravi in the comments.

This problem can be solved in another way which still uses a $\Theta(n \lg n)$ sorting procedure but instead of using $\textsc {Binary-Search}$, it uses a two-way search, i.e. simultaneous search from both end of the array, to check if two elements sums up to expected sum, $x$.

$$\textsc {Sum-Search }(S, x)$$$$\begin{aligned}1& \quad \textsc {Merge-Sort}(S,\,1,\,S.length) \\2& \quad left=1 \\3& \quad right=S.length \\4& \quad \textbf {while }\textsc {}(left<right) \\5& \quad \qquad \textbf {if }S[left]+S[right]==x \\6& \quad \qquad \qquad \textbf {return }true \\7& \quad \qquad \textbf {else }\textbf { if }S[left+S[right]<x \\8& \quad \qquad \qquad left=left+1 \\9& \quad \qquad \textbf {else } \\10& \quad \qquad \qquad right=right-1 \\11& \quad \textbf {return }false \\\end{aligned}$$