c++ - The intersection of two sorted arrays

Question

Given two sorted arrays: A and B. The size of array A is La and the size of array B is Lb. How to find the intersection of A and B?

If La is much bigger than Lb, then will there be any difference for the intersection finding algorithm?

Answer 1

Since this looks like a HW...I'll give you the algorithm:

Let arr1,arr2 be the two sorted arrays of length La and Lb.
Let i be index into the array arr1.
Let j be index into the array arr2.
Initialize i and j to 0.

while(i < La and j < Lb) do

    if(arr1[i] == arr2[j]) { // found a common element.
        print arr[i] // print it.
        increment i // move on.
        increment j
    }
    else if(arr1[i] > arr2[j])
        increment j // don't change i, move j.
    else
        increment i // don't change j, move i.
end while