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

March 8, 2011 Leave a comment

**APPROACH 2 **

The previous approach had a running time of . (In terms of memory requirements, it was optimal, using 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, of length , and an int , 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 are distinct.

How would we go about doing it?

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

So, what we want to do is to search for a number – , in our case – in a sorted array. We can apply binary search, which would take time.

Therefore, we take time processing .

We then proceed to and search for in . That again takes time.

As you would have guessed by now, we take time for each of the elements of , and hence the running time would be .

Now, since the original array in question is not sorted, we would first need to sort, which would take time.

Hence the running time complexity of the algorithm is .

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 .

———-

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] << ” }”;
**

**}
**

**}**

**————**