Question

Let $A = \{ a_1, . . . , a_n \}$ and $B = \{b_1, . . . , b_m\}$ be two sets of numbers. Consider the problem of finding their intersection, i.e., the set C of all the numbers that are in both A and B. Design a presorting-based algorithm in **pseudo code** for solving this problem and determine its efficiency class.

Answer 1

Answer: Pseudo code

Initialize intersection I as empty.

Find smaller of m and n and sort the smaller array.

function printIntersection(int arr1[ ], int arr2[ ], int m, int n)

{

// Before finding intersection, make sure arr1[0..m-1]

// is smaller

if (m > n)

{

int *tempp = arr1;

arr1 = arr2;

arr2 = tempp;

int temp = m;

m = n;

n = temp;

}

// Now arr1[ ] is smaller

// Sort smaller array arr1[0..m-1]

sort(arr1, arr1 + m);

// Search every element of bigger array in smaller

// array and print the element if found

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

if (binarySearch(arr1, 0, m-1, arr2[i]) != -1)

cout << arr2[i] << " ";

}

3) For every element x of larger array, do following

…….b) Binary Search x in smaller array. If x is present, then copy it to I.

int binarySearch(int arr[], int l, int r, int x)

{

if (r >= l)

{

int mid = l + (r - l)/2;

// If the element is present at the middle itself

if (arr[mid] == x) return mid;

// If element is smaller than mid, then it can only

// be presen in left subarray

if (arr[mid] > x)

return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right subarray

return binarySearch(arr, mid+1, r, x);

}

// We reach here when element is not present in array

return -1;

}

4) Return I.

Step-by-step explanation:

Time complexity of this method is min(mLogm + nLogm, mLogn + nLogn) which can also be written as O((m+n)Logm, (m+n)Logn). This approach works better than the different approaches like hashing when difference between sizes of two arrays is significant.