Find if a sum of any two elements is set S is equal to given x in nlgn

I got a little problem with this excercise from Introduction to Algorithms (Cormen et al.).

Given a set S of n integers, and an integer x, describe an algorithm of time complexity n*lg(n) which finds if sum of any two elements from S are equal to x.

Examining every pair gives n*n algorithm, which is not what I want.
I think a merge-sort like algorithm could be used, but have no idea how to check if there are two such elements in two subsets (the merge step) in linear time. But maybe the whole idea is wrong. If someone can give any hints on this, I'd appreciate it =)

Oh. My second idea is a 2*n*lg(n) algorithm given below.

merge-sort(S) // takes n*lg(n)
for each y in S: // n times
r = x - y
binary-search(S, r) // takes at most lg(n)
if found then return

If anyone knows a better (faster) solution please let me know.

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!