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

}

}

————

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

%d bloggers like this: