Checking if there are 2 elements in an array that sum to X in O(n lg n)

Problem Detail: 

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this solution is $O(n^2)$.

My solution is: Say the array is A. It's length is N. Elements are from A[0] to A[N-1]

Pseudo-Code is:

Check_Sum(A,left,right) {   mid <-- floor( (left+right)/2 )    if(A[left]+A[right]=X)     return true    return Check_Sum(A,left,mid)||Check_Sum(A,mid,Right) } 

My question is: Is the complexity of my solution equal to $O(n \lg n)$?

Asked By : Trinarics

Answered By : SameeraGupta

Sort the array say ascending order- Takes O(nlogn)

Keep two pointers in the array say fingers. Finger f1 at the first element and finger f2 at the last element.

Sum the elements to get f1+f2: if f1+f2 == X you have found your solution else if f1+f2 > X decrease f2 to point to the element to its left else increase f1 to point to the element to its right

This step will take O(n) making the overall cost O(nlogn)

This solution is also referred to as the finger pointing solution. Can be used in any sorted collection where you can traverse in both the direction for eg in trees.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21858