Search for Intersection Between Two Sorted Arrays of Integers | Code Samurai

Search for Intersection Between Two Sorted Arrays of Integers | Code Samurai

Search for Intersection Between Two Sorted Arrays of Integers

Question: there are two sorted arrays of integers such as array(1, 3, 6, 9, 10) and array(-2, 0, 4, 6, 12). Search for the intersection between these arrays. The intersection is 6 at index 2 and index 3 in the example arrays.

Solution: a naive solution would be to compare each element in the first array to each element in the second array, resulting in an O(N * M) algorithm where N and M are the numbers of elements in first and second array respectively. A better solution is using binary search for each element in the first array in the second array. That is an O(N LogM) algorithm. However, we can even do better using two array iterators at a time. Take a look at the pseudocode below:

it1, it2  while it1 < size1 and it2 < size2    if (array1[it1] == array2[it2])      print(it1 and it2)      return    else if (array1[it1] > array2[it2])      it2++    else      it1++  

We simply move the iterators, one for each array, whenever an element of one array is less that the element of the other array. We do this until we either find the common element (intersection) or we reach the end of any array. This works because both arrays are sorted in the ascending order. Thus, we don't have to compare each and every element to all other elements to know where the intersection is. Here is the implementation of the pseudocode in JavaScript :)

function vIntersectionInSortedArrays(cIntArray1, cIntArray2)  {     if (cIntArray1 === null || cIntArray1 === undefined         || cIntArray2 === null || cIntArray2 === undefined)     {        document.write("Empty arrays!");         return;     }       var nArray1It = 0;     var nArray2It = 0;          while (nArray1It < cIntArray1.length            && nArray2It < cIntArray2.length)     {        if (cIntArray1[nArray1It] == cIntArray2[nArray2It])        {           document.write("Intersect at index" + nArray1It                           + " and " + nArray2It);           return;        }        else if (cIntArray1[nArray1It] > cIntArray2[nArray2It])           nArray2It++;        else           nArray1It++;     }       document.write("No intersection!");  }  

I know it's unusual to use JavaScript but a break from C++ and Java is nice. As we expect, this algorithm is more efficient. In the worst case, it takes only O(M + N) time to return the answer!

As always, thanks for following and if you have any suggestion, please don't hesitate to let me know in the comment section.

Read full article from Search for Intersection Between Two Sorted Arrays of Integers | Code Samurai