# finding a & b in an array that a+b = x, for a given integer x [closed]

I want to get an algorithm with $\theta(nlogn)$ time complexity that search for two elements in an array of integers, which their sum is equal to $x$ such that x is an integer and $n$ is array size.

• Great, good luck! – Yuval Filmus Nov 1 '16 at 21:59
Hint. Sort the array. That can be done in $\Theta(n\log n)$ time. Then, for each element, $a$, in the array find out if $x-a$ is in the array. Can you do those searches quickly? If you can do each search in time $\Theta(\log n)$, for instance, then that will add on no more than $\Theta(n\log n)$ to your running time.