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

Howdy, Stranger!

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

Categories

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

Hi!
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.

regards
LaChupacabra
Sign In or Register to comment.