Saturday, July 19, 2008

Do two elements in a sorted array sum up to a value?

#include <vector>
#include <iostream>

using namespace std;

pair* find2Elems(vector& a, size_t len, int findme)
{
int iFront = 0, iBack = len-1, sum;
while (iFront < iBack)
{
sum = a[iFront] + a[iBack];
// sum is too large
if (sum > findme)
{
iBack--;
}
// sum is too small
else if (sum < findme)
{
iFront++;
}
else // if (sum == findme)
{
return new pair(iFront,iBack);
}
}
return NULL;
}

int main() {
const size_t size = 20;
vector a(size);
srand(time(NULL));
// make a vector with random elements
for (int i=0; i < size; i++)
{
a[i] = rand()%50;
}
sort(a.begin(), a.end());
for (int i=0; i < size; i++)
cout << a[i] << " ";
cout << endl;
pair *p = find2Elems(a, size, 20);
if (p)
{
cout << a[p->first] << ", " << a[p->second] << endl;
}
else
cout << "not found" << endl;
return 0;
}

No comments: