VB.NET Array Intersection

Question

This could be terribly trivial, but I'm having trouble finding an answer that executes in less than n^2 time. Let's say I have two string arrays and I want to know which strings exist in both arrays. How would I do that, efficiently, in VB.NET or is there a way to do this other than a double loop?

Answer 1

The simple way (assuming no .NET 3.5) is to dump the strings from one array in a hashtable, and then loop through the other array checking against the hashtable. That should be much faster than an n^2 search.

Answer 2

If you sort both arrays, you can then walk through them each once to find all the matching strings.

Pseudo-code:

while(index1 < list1.Length && index2 < list2.Length)
{
   if(list1[index1] == list2[index2])
   {
      // You've found a match
      index1++;
      index2++;
   } else if(list1[index1] < list2[index2]) {
      index1++;
   } else {
      index2++;
   }
}

Then you've reduced it to the time it takes to do the sorting.