Union and Intersection of two sorted arrays | GeeksforGeeks

Union and Intersection of two sorted arrays | GeeksforGeeks
Algorithm Union(arr1[], arr2[]):
For union of two arrays, follow the following merge procedure.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then print arr1[i] and increment i.
3) If arr1[i] is greater than arr2[j] then print arr2[j] and increment j.
4) If both are same then print any of them and increment both i and j.5) Print remaining elements of the larger array.

int printUnion(int arr1[], int arr2[], int m, int n)

{

  int i = 0, j = 0;

  while(i < m && j < n)

  {

    if(arr1[i] < arr2[j])

      printf(" %d ", arr1[i++]);

    else if(arr2[j] < arr1[i])

      printf(" %d ", arr2[j++]);

    else

    {

      printf(" %d ", arr2[j++]);

      i++;

    }

  }

  /* Print remaining elements of the larger array */

  while(i < m)

   printf(" %d ", arr1[i++]);

  while(j < n)

   printf(" %d ", arr2[j++]);

}

Algorithm Intersection(arr1[], arr2[]):
For Intersection of two arrays, print the element only if the element is present in both arrays.
1) Use two index variables i and j, initial values i = 0, j = 0
2) If arr1[i] is smaller than arr2[j] then increment i.
3) If arr1[i] is greater than arr2[j] then increment j.
4) If both are same then print any of them and increment both i and j.

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

{

  int i = 0, j = 0;

  while(i < m && j < n)

  {

    if(arr1[i] < arr2[j])

      i++;

    else if(arr2[j] < arr1[i])

      j++;

    else /* if arr1[i] == arr2[j] */

    {

      printf(" %d ", arr2[j++]);

      i++;

    }

  }

}

http://leetcode.com/2010/03/here-is-phone-screening-question-from.html

Compare this approach with the binary search approach.
O(m+n) and O(m*lg(n))

lg(n) is much smaller than n when n is very big. However, this does not necessarily means binary search is better in this case. In fact, binary search approach is only better when m << n (m is very small compared to n). For example, when m = 1 and n = one billion, which method will you choose? Binary search is definitely the winner here.

i) What if elements of array B is stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
ii) How will the complexity change in this case? Are there any factors you need to consider? 
iii) How do you change your solution to adapt to this situation?

Read full article from Union and Intersection of two sorted arrays | GeeksforGeeks