Find intersection of two sorted integer arrays if one array is very large in size than other
  • Posted: 4 years ago
  • Updated: 3 years ago
  • Edit
  • answers (1)
  • views (2138)

Write the algorithm in Find intersection of two sorted integer arrays when one array is very large in size than the other one.


Posted Answers

When one array is very large and the other one is very small we can use binary search. Suppose array1 [ ] has m and array2 [ ] has n number of elements respectively where m < < n . We can iterate through array1 [ ] (since it has less number of elements) and binary search for that element in array2 [ ].

Time complexity = \( O(mlogn) \).

public static void findIntersectionOflargearray(int[] array1, int[] array2, int m, int n) {

/* loop for all numbers in a small array: array1[] */
for (int i = 0; i < m; i++) {
/* perform binary search on the large array : array2[] */
if (binarySearch(array2, array1[i], 0, n) != -1)
system.out.println("%d ", array1[i]);
}
}

public static int binarySearch(int array[], int number, int start, int end) {

if (end < start)
return -1;
int mid = (start + end)/2;
if (a[mid] > number)
return binarySearch(array, number, start, mid-1);
else if (a[mid] < number)
return binarySearch(array, number, mid+1, end);
else
return mid;
}

You need to Sign In to post your solution.