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.
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.
