Your program will take two unsorted arrays, A (size = m) and B (of size = n) as the input and find
the union and intersection of A and B (see below for definition). You can
assume that the values within the arrays, A
and B, are always distinct.
Definition:
· Union:
The union of two arrays, A and B is computed as below:
o
All values in A and the
values in B that do not occur in A.
· Intersection:
The intersection of two arrays, A and
B is given by the values that occur
in both A and B.
Example:
Array, A: 8 2 7 9 34 14
Array, B: 3 2 7 8
Union of A and B:
2 3 7
8 9 34 14
Intersection of A and B:
8 2 7
Algorithm:
Before you implement Method #3 for this problem (see below), read
through the algorithms presented in Method #1 and Method#2:
Method #1
- Brute-force (will be explained in class):
· We could
use a nested loop and find values for union and intersection as defined above.
· The
running time would be O (n * m) and
the space utilization would be O (1).
Method #2
– Sorting + linear search (will be explained in class):
·
We could sort A and B using
merge sort for a running time of O(m log
m) + O( n log n) and a space
utilization of O(m) + O(n) =
O(m + n).
·
Using a single loop, we could parse through the sorted arrays and print
the values of union and intersection in a running time of O (m + n).
·
The total running time would be O (m
log m) + O (n log n) + O (m + n) = O (m log m) + O (n log n).
·
The space utilization would be O (m
+ n).
Method #3
– Sorting + binary search (will be explained in class):
1)
We will find the smaller (in terms of size) of two arrays, A (size, m =
6) and B (size, n = 3). In our example, B is the smaller array. We will now
sort B.
2)
To find union of A and B:
a.
Print the values in B.
b.
Loop through each value, V in A
: O(m)
{
Binary
search for V in B: O (log n)
{
If V is
not found in B, print V.
}
}
3)
To find intersection of A and B:
a.
Loop through each value, V in A:
O(m)
{
Binary
search for V in B: O
(log n)
{
If V is
found in B, print V.
}
}
Running time for
Method #3:
· Step #1: Using merge
sort, we can sort B in a running
time of O (n log n) and a space
utilization of O (n).
· Step #2
and Step #3 have a running time of O (m
log n).
· Since
Steps, #1, #2 and #3 executed sequentially, the total running time is O (n log n) + O( m log n), where n is the
size of the smaller array and m is
the size of the larger array.
Space utilization for
Method #3:
·
We will need O (n) to implement merge sort on the
smaller array, B (size = n).
The reference program below contains the methods for binary search and
merge sort: