Mailing List Archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

On 4/18/07, Chris BALUTA <> 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)

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
VIQR Standard:

Home | Main Index | Thread Index

Home Page Mailing List Linux and Japan TLUG Members Links