Re: [tlug] array duplicate check [C]

[baluta@example.com (Chris BALUTA)]

 Nguyen Hung Vu asks:

> I have two integer arrays  of size N and M and I want to check if none
> of the elements in the first arrays are contained in the second array.
> The programming language is pure C so no vector or set like Java.
 
  [snip, pseudo code]

> whose the complexity is N*M in the worst case. The performance will be
> a pain if N or M grow big.
> 
> So how can I improve the algorithm? ( for the worst case ) I have a
> feeling that I can reduce the complexity to N or M...

    Are either of the arrays sorted? I'm not up on algoritms
so I can't say the cost of sorting an array, but if it's not
too expensive, sort one of the arrays (the smaller), if they
already aren't sorted.

    Once one of the arrays is sorted, you can then do a
binary search over the sorted array for each element of the
unsorted one:

   for k=1, N
     if ( binarySearch (unsortedArray[k], sortedArray) == 1)
       fail;
   endfor
 
  The cost here is, I believe, N * lg(M) (as opposed to N*M).


       -Chris