Two numbers in a array that add up to a given number

You are given a array, and a number M. Your goal is to find out which two numbers in the array when added up gives M.

Answer:

Step 1. Sort the array in O(n log (n) )
Step 2. Assuming the number is 50,

Optimization of Step 1:
Instead of sorting the complete array,
- Create the heap
- Remove the root until we hit a number k, such that k >= M
- This will be better than sorting the entire array.

down     up
|         |
10 15 20 30 [50] 90

while ( down < up )
{ 
  if ( a[down] + a[up] > a[num] ) --up;
  else if ( a[down] + a[up] < a[num] ) ++down;
  else /* we found a pair */
}