Re: [tlug] array duplicate check [C] [ Solved ]

["Nguyen Vu Hung" <vuhung16plus@example.com>]

On 4/18/07, Chris BALUTA <baluta@example.com> wrote:
>    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).
Exactly what I need. Your solution is indentical to BAB's.

The raw data is not sorted, but since they are loaded into memory so
the cost for sorting one of the array is cheap ( log M ).

--
Best Regards,
Nguyen Hung Vu
vuhung16plus{remove}@example.com
VIQR Standard: http://vi.i18n.kde.org/viqr
http://www.flickr.com/photos/vuhung/tags/fav/