Union and Intersection of two sorted arrays

Given two sorted arrays, find their union and intersection.

For example, if the input arrays are: 
arr1[] = {1, 3, 4, 5, 7}
arr2[] = {2, 3, 5, 6}
Then your program should print Union as {1, 2, 3, 4, 5, 6, 7} and Intersection as {3, 5}.

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.

#include<stdio.h>   /* Function prints union of arr1[] and arr2[]    m is the number of elements in arr1[]    n is the number of elements in arr2[] */ 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++]); }   /* Driver program to test above function */ int main() {   int arr1[] = {1, 2, 4, 5, 6};   int arr2[] = {2, 3, 5, 7};   int m = sizeof(arr1)/sizeof(arr1[0]);   int n = sizeof(arr2)/sizeof(arr2[0]);   printUnion(arr1, arr2, m, n);   getchar();   return 0; }

Time Complexity: O(m+n)

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.

#include<stdio.h>   /* Function prints Intersection of arr1[] and arr2[]    m is the number of elements in arr1[]    n is the number of elements in arr2[] */ 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++;     }   } }   /* Driver program to test above function */ int main() {   int arr1[] = {1, 2, 4, 5, 6};   int arr2[] = {2, 3, 5, 7};   int m = sizeof(arr1)/sizeof(arr1[0]);   int n = sizeof(arr2)/sizeof(arr2[0]);   printIntersection(arr1, arr2, m, n);   getchar();   return 0; }

Time Complexity: O(m+n)

Another approach that is useful when difference between sizes of two given arrays is significant.
The idea is to iterate through the shorter array and do a binary search for every element of short array in big array (note that arrays are sorted). Time complexity of this solution is O(min(mLogn, nLogm)). This solution works better than the above approach when ratio of larger length to smaller is more than logarithmic order.

See following post for unsorted arrays.
Find Union and Intersection of two unsorted arrays

Please write comments if you find any bug in above codes/algorithms, or find other ways to solve the same problem.