The 2-Sum problem

Input : Unsorted array A of n Integers, Target Sum t.

Goal : Determine whether or not there are two numbers x,y in A with x + y = t.

Naive Solution : O(n^2) time via exhaustive serach.

Better :
1) Sort A  O(nlogn)
2) For each x in A' look for t - x in A via binary search.  O(nlogn)  

Amazing :