• 5

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

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

  • Posted: 7 years ago
  • 0 4
  • Edit

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.