Find two elements with certain sum in a sorted array

Given a sorted array A[n], find out if there exist two elements whose sum is equal to S. The complexity of the algorithm needs to be O(n).

C++:
01 void equalsum(int *A, int size, int S,  int& a, int &b)
02 {
03     int p=0;
04     int q=size1;
05     while(p<q){
06         if((A[p]+A[q])==S){
07             a=p;
08             b=q;
09             return;
10         }
11         if((A[p]+A[q])>S)
12             q;
13         if((A[p]+A[q])<S)
14             p++;
15     }
16     a=-1;
17     b=-1;
18     return;
19 }
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s