Fastes way to do binary search

  • Thread starter Thread starter Soeren S. Joergensen
  • Start date Start date
S

Soeren S. Joergensen

Hi,

I've got to byte arrays, and want to search first array for the position of
the first occurance of the other.

How is this best implemented ?

Kr. Soren
 
Hi,

I've got to byte arrays, and want to search first array for the position of
the first occurance of the other.

How is this best implemented ?

Kr. Soren
Click to expand...

First of all, don't call it binary search. Binary search already has
another meaning. :)

Anyway, it is pretty straight forward. You use brute force. Start on
the first byte of the first array and see if the second array matches
at that position. If it doesn't try the second byte, and so on.
 
First of all, don't call it binary search. Binary search already has
another meaning. :)
Click to expand...

Sorry :)
Anyway, it is pretty straight forward. You use brute force. Start on
the first byte of the first array and see if the second array matches
at that position. If it doesn't try the second byte, and so on.
Click to expand...

Well, that's also my first aproach.
But first array could potentially be rather large, and second array might
not exist, so the iteration time could take a while.
I hoped some clever head had thought oif a way to optimize such a task.

Anyway, thanx...

Soren
 
Soeren said:
Hi,

I've got to byte arrays, and want to search first array for the position of
the first occurance of the other.

How is this best implemented ?
Click to expand...

I think you could try to implement the boyer moore string searching
algorithm if you need a "best implementation". Check google or wikipedia
for an explanation of how it works.

hth,
Max
 
It depends.... If you are going to do multiple searches over time for
values in a
fairly stable array, then it may be more efficient to create a sorted
index and do
a binary search on the index. .NET has built in support for collections
with both
ordinal access and indexed access on a key.

Regards,
Jeff
I've got to byte arrays, and want to search first array for the
Click to expand...
position of
the first occurance of the other.

How is this best implemented ?<
 
Hi,

I've got to byte arrays, and want to search first array for the position of
the first occurance of the other.

How is this best implemented ?

Kr. Soren
Click to expand...

It seems to me that what you are doing is a bit like string searching:

Given array1 = ABCDEFGHIJKLMNOP

and array2 = GHI

find the first position of array2 in array1.

Search for Boyer-Moore Algorithm, Knuth-Morris-Pratt algorithm or
Rabin-Karp algorithm. One of them should help you.

rossum



The ultimate truth is that there is no ultimate truth
 
Hi,

Seems like Boyer-Moore Algorithm will fit my needs and is fairly easy to
implement :)

Thanx all...

Kr. Soren
 
Back
Top