Intersection of two sorted lists or 2 sorted arrays

For two sorted lists,
1, 2, 12, 15, 17, 18
1, 12, 14, 15, 16, 18, 20
intersection is bold numbers.

Solution 1 : Brute force
 An intuitive solution for this problem is to check whether every number in the first array (denoted as array1) is in the second array (denoted as array2). If the length of array1 is m, and the length of array2 is n, its overall time complexity is O(m*n) based on linear search. We have two better solutions.

Solution 2 : Take the benefit of sorting of array
It is noticeable that the two input arrays are sorted. Supposing a number number1 in array1 equals to a number number2 in array2, the numbers after number1 in array1 should be greater than the numbers before number2 in array2. Therefore, it is not necessary to compare the numbers after number1 in array1 with numbers before number2 in array2. It improves efficiency since many comparisons are eliminated.

List getIntersection(int[] a, int[] b){
    int apos = 0, bpos = 0
    List intersection
    while apos < a.length && bpos < b.length:
        if a[apos] == b[bpos]:
            intersection.add(a[apos])
            apos++, bpos++
        else:
            if a[apos] < b[bpos]:
                apos++
            else:
                bpos++
    return intersection 
}

Time Complexity is O(m + n).
Since it only requires to scan two arrays once, its time complexity is O(m+n).


Note: Using an ArrayList wastes space, instead use LinkedList.

Solution 3 - Using binary search in O(n log m) time

As we know, a binary search algorithm requires O(logm) time to find a number in an array with length m. Therefore, if we search each number of an array with length n from an array with length m, its overall time complexity is O(nlogm). If m is much greater than n, O(nlogm) is actually less than O(m+n). Therefore, we can implement a new and better solution based on binary search in such a situation. 

For instance, the following same code is suitable when array1 is much longer than array2.

 /* === Supposing array1 is much longer than array2 === */
void getIntersectionUsingBinarySearch(int[] array1,
                     int[] array2,
                     int[] intersection)
{
    intersection.clear();
   
    int iter1 = array1[0];
    while(iter1 != array1[array1.size-1])
    {
        if(binary_search(0, array2.size, iter1))
            intersection.add(iter1);
    }
}

Time complexity : n log (m)

Thanks.