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.