Given an array A of n integers, in sorted order, and an integer x.
design an O(n)-time complexity algorithm to determine whether there
are 2 integers in A whose sum is exactly x.

This looks pretty simple. You need two pointers to the array; start
one at the beginning and one at the end. I'm assuming the integers are
stored in ascending order; the modifications for descending order
should be pretty clear.

1. Get value at start pointer, call it s. 
2. Get value at end pointer, call it e.
3a. If e is equal to x - s, return success.
3b. If e is greater than x - s, decrement the end pointer. If end
pointer is before start pointer, return failure; else go to 2.
3c. If e is less than x - s, increment the start pointer. If start
pointer is after end pointer, return failure; else go to 1.

Basically we're being smart about which potential partners we look at
for each candidate. At each iteration we narrow the gap between start
and end pointers by 1, so we execute n iterations at most and we don't
have an interior loop, so it's O(n).

#include <iostream>
using namespace std;

int solve (int A[], int n, int x);
int main()
{
	int A[]={1,2,3,4,5,6,7,8,9,10};
	int x= 5;
	solve(A,10,x);
	x=232;
	solve (A,10,x);
}

int solve (int A[], int n, int x)
{
	int *B;
	int i,j;
	B=new int[n];

	for (i=0, j=n-1  ;i<n;i++, j--)
	{
		B[j]=A[i]-x;
	}
	for (i=0;i<n;i++)
	{
		if (A[i]==B[i])
		{
			//answer is true
			delete [] B;
			cout<<endl<<"There are two numbers in array with sum = "<<x<<endl;
			return (1);
		}
	}

	delete [] B;
	cout<<endl<<"There are no two numbers in array with sum = "<<x<<endl;
	return (0);
}

There is a little ambiguity in the problem formulation, because
"determine whether there are 2 integers in A whose sum is exactly x"
might mean that we seek two distinct integers and that it is forbidden
to use the same integer twice.  I'd ask the instructor to clarify
which interpretation was intended.

Assuming the same entry can be used twice, manuka-ga's analysis is
correct.  Rather than check all n*(n+1)/2 possible pairs, manuka-ga's
approach is "adaptive" and uses information from the "failure" of
previous steps to prune the search space down to O(n).  Also, the
logic is easily revised, should the instructor say that the same entry
cannot be used twice.

If I'm interpreting bighugegamer-ga's code correctly (and
acknowledging that the indexing there is C-style/zero-based), B[i] is
assigned value A[n-i-1] - x.  It then checks whether for some index i:

  A[i] == B[i], equiv.  A[i] == A[n-i-1] - x

This doesn't give a way of expressing x as the sum of two entries in
A, but if B[i] were instead assigned x - A[n-i-1], then:

  A[i] == B[i]  implies  A[i] == x - A[n-i-1]

and within the limitations of computer arithmetic, x is A[i] + A[n-i-1].

While this would at least give a possibility to find a solution, those
are not the only candidates that need to be checked.  For example, x
might be expressible, to use the n = 5 test case, as A[3] + A[4].

A picture might be helpful.  Consider the n-by-n array of all possible
sums of pairs from array A:

  A[1] + A[1] ...  A[1] + A[j] ... A[1] + A[n]
      ...              ...             ...
  A[i] + A[1] ...  A[i] + A[j] ... A[i] + A[n]
      ...              ...             ...
  A[n] + A[1] ...  A[n] + A[j] ... A[n] + A[n]

bighugegamer-ga's code roughly does a search across only one of the
anti-diagonals, potentially overlooking solutions.  manuka-ga's
strategy overcomes that kind of limitation by making a zig-zag search
pattern.

Essentially manuka-ga's search starts at one of the "outside" corners
(since addition is commutative, the matrix above is symmetric and only
half of it needs to be searched).

Both the rows and the columns of this matrix are in sorted order
(ascending, for the sake of discussion).  The search strategy outlined
by manuka-ga says, if the currently search entry is equal to x, we're
done.  Otherwise, decrease the row if we are too high or increase the
column if we are too low.  Stop with "failure" if this movement would
take us out of the matrix (or across the main diagonal, by symmetry).


regards, mathtalk-ga