Question

Do not copy from others! Thank you!

Design an algorithm to find all the common elements in two sorted lists of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the output should be 2, 5, 5. What is the maximum number of comparisons your algorithm makes if the lengths of the two given lists are m and n, respectively?

Answer 1

Algorithm:

Input sorted lists A,B

1.set index i,j to 0.i used the index on array A and j used the index of array B

2.Repeat untill i<m and j<n

i.if A[i]<B[j] then increment i.

ii.Else if B[j]<A[i] then increment j.

iii.else print the number A[i] and increment both i and j.

3.End

Algorithm:

commonelements(A,B,m,n)
{
   i=0,j=0
   while(i<m && j<n)
   {
       if(A[i]<B[j]) then i++
       else if(B[j]<A[i]) then j++
       else print(A[i]),i++,j++
   }
}

The maximum number of comparisons the algorithm make is O(m+n).

If you have any queries, please comment below.

Please upvote , if you like this answer.