Find common elements in two sorted arrays

Suppose arr1[] = {2,4, 6, 8, 10, 11, 23, 45, 67} and arr2[] = {11, 25, 29, 43, 45, 67, 70, 80}.

Common elements between arr1 and arr2 are {11, 45, 67}.

To solve this problem, we can utilize the sorted property of elements.

Approach 1

Since elements are sorted. We can apply simple binary search to find common elements. Suppose arr1 has n elements, and arr2 has k elements. Iterate through arr2 and use binary search to find whether element of arr2 is in arr1 or not.

for(i in arr2){

         if(binarySearch(arr1, i))

                  add element to list

}

Approach 2

We can apply merge logic of merge sort here. Start with two counters (counter1=0, counter2=0) pointing to beginning of the arrays. If the elements pointed by these counters are same, then it is a common element, and we advance both the counters. If one element is smaller, then advance that counter. Continue this until any one counter reaches end.

import java.util.ArrayList;
import java.util.List;

public class CommonElements<T extends Comparable<T>> {

 public List<T> getCommonElements(T arr1[], T arr2[]) {
  List<T> commonElements = new ArrayList<>();

  int counter1 = 0, counter2 = 0;

  while (counter1 < arr1.length && counter2 < arr2.length) {
   if (arr1[counter1].equals(arr2[counter2]))
    commonElements.add(arr1[counter1]);

   if (arr1[counter1].compareTo(arr2[counter2]) < 0)
    counter1++;
   else
    counter2++;
  }

  return commonElements;

 }
}

Following is the junit test case for above program.

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class CommonElementsTest {

 @Test
 public void test1() {
  CommonElements<Integer> obj1 = new CommonElements<>();

  Integer arr1[] = { 2, 4, 6, 8, 10, 11, 23, 45, 67 };
  Integer arr2[] = { 11, 25, 29, 43, 45, 67, 70, 80 };

  List<Integer> actual = obj1.getCommonElements(arr1, arr2);

  assertEquals(Arrays.asList(11, 45, 67), actual);
 }
}