# Arrays in C++ – Finding appropriate pairs in an array – 2

APPROACH 2

The previous approach had a running time of $O(n^2)$. (In terms of memory requirements, it was optimal, using $O(1)$ space.)

The question is whether we can do better in terms of running time.

As a thought experiment, assume that we have a sorted array, $S$ of length $n$, and an int $target$, and that we have to perform the same task as was assigned to us earlier. Also, for simplicity, let us assume that all elements in $S$ are distinct.

How would we go about doing it?

We could approach it as follows — Take the first element of $S$. Subtract it from $target$ to get a new number say $x$. Now, if x is indeed part of $S$, we would need to output the pair $S[0], x$.

So, what we want to do is to search for a number – $x$, in our case – in a sorted array. We can apply binary search, which would take $O( \log n)$ time.

Therefore, we take $O( \log n)$ time processing $S[0]$.

We then proceed to $S[1]$ and search for $target - S[1]$ in $S$. That again takes $O( \log n)$ time.

As you would have guessed by now, we take $O( \log n)$ time for each of the $n$ elements of $S$, and hence the running time would be $O ( n \log n)$.

Now, since the original array in question is not sorted, we would first need to sort, which would take $O( n \log n)$ time.

Hence the running time complexity of the algorithm is $O( n \log n)$.

We assume that we do not want to modify the array passed to the function. Hence, we would use separate storage for the sorted array. That would mean a memory usage of $O(n)$.

———-

Let us try to write the above method in C++:-

#include <iostream>

#include <vector> //This automatically implies “#include <algorithm>”. So we need not explicitly write that.

using namespace std;

//func f takes int array A, length n of A, and an int target.

// It outputs all pairs of elements in A which sum to target.

void f ( int * A, int n, int target)

{

vector <int> v;

copy (A, A+n, inserter (v, v.begin( ) ) ); //we would need to use this syntax for copying in insert mode.

sort (v.begin ( ), v.end ( ) ); // Now v has the elements of A in ascending order.

//we can now use the find algorithm or write our own function, bin_search, for binary search.

for ( int i = 0; i < n; i++)

{

if (bin_search (v, target – A[i]) )

cout << “{  ” << A[i] << “, ” << target – A[i] << ” }”;

}

}

————