Given two sorted arrays, how do you efficiently find the common elements between those two?

Method#1: Simple and Brute-force approach

Iterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we doing a linear search in the second array which takes O(n). So for n elements it would be O(n^2).

Method#2: Better approach with binary search

This approach is simliar to the first one except that it uses binary search instead of linear search for finding an element in the second array as the arrays are sorted. Binary search takes O(log n) for each element. So for n elements the time complexity would be O(n log n).

Method#3: Efficient

This method fully utilizes the fact that both arrays are sorted. Start with two indices pointing to beginning of the arrays. If the elements pointed by these indices are same, then it is a common element, and we advance both the pointers. If one element is smaller, then advance that pointer (in hope of finding the next equal element). Continue this until any one of the two indices reaches their end.

Here is the C++ code which implements the third approach.

#include <iostream>

#include <string>

#include <vector>

using namespace std;

//prints the intersection of two sorted arrays

//duplicates are allowed

void printIntersect(vector<int>& s1, vector<int>& s2)

{

//i and j start 0 i.e first element

int i = 0 , j= 0;

//while either of the two indices reaches end

while ( i < s1.size() && j < s2.size() )

{

//if first array element is lesser, advance that index by one

if( s1[i] < s2[j] )

{

i++;

}

//otherwise advance second index

else if( s1[i] > s2[j] )

{

j++;

}

//both elements are same, print it, and advance both the pointers

else

{

cout<<s1[i]<<" ";

i++;

j++;

}

}

}

int main()

{

vector<int> set1, set2;

int n1,n2; //size of the sets

cin>>n1>>n2;

int i;

//read two arrays

for( i = 0 ; i < n1; i++ )

{

int d;

cin>>d;

set1.push_back(d);

}

for( i = 0 ; i < n2; i++ )

{

int d;

cin>>d;

set2.push_back(d);

}

printIntersect(set1,set2);

return 0;

}