Linear time algorithm for 2-SUM

Question

Given an integer x and a sorted array a of N distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i] + a[j] == x

Answer 1

This is type of Subset sum problem

Here is my solution. I don't know if it was known earlier or not. Imagine 3D plot of function of two variables i and j:

sum(i,j) = a[i]+a[j] 

For every i there is such j that a[i]+a[j] is closest to x. All these (i,j) pairs form closest-to-x line. We just need to walk along this line and look for a[i]+a[j] == x:

 int i = 0;   int j = lower_bound(a.begin(), a.end(), x)  -  a.begin();   while (j >= 0 && j < a.size()  &&  i < a.size())  {       int sum = a[i]+a[j];      if (sum == x)   {          cout << "found: " << i << " " << j << endl;           return;     }     if (sum > x)    j--;     else            i++;     if (i > j) break;  }    cout << " not found\n"; 

Complexity: O(n)