ASAP: Binary search algorithm

[Peter Schmitz]

Hi,

one of the main task of my currently developed application is to search in
small buffers for given patterns (average buffer size 1000 bytes). Now, for
some reasons I can't use the provided C std libs, so I need to implement my
own - but unfortunately I cannot find any hints about how to program such an
algorithm, so that it is really fast. Is there any (free) algorithm to start
with? Any free implementations?

Thanks a lot for any help
Peter

[Hendrik Schober]

Peter Schmitz <Pe**********@discussions.microsoft.com> wrote:

Hi,

one of the main task of my currently developed application is to search in
small buffers for given patterns (average buffer size 1000 bytes). Now, for
some reasons I can't use the provided C std libs, so I need to implement my
own - but unfortunately I cannot find any hints about how to program such an
algorithm, so that it is really fast. Is there any (free) algorithm to start
with? Any free implementations?
Can you use the C++ std lib? There's
'std::binary_search()' in <algorithm>.
Thanks a lot for any help
Peter

Schobi

--
Sp******@gmx.de is never read
I'm Schobi at suespammers dot org

"The presence of those seeking the truth is infinitely
to be prefered to those thinking they've found it."
Terry Pratchett

[Vincent Finn]

On Fri, 19 Nov 2004 13:49:06 -0800, "Peter Schmitz"
<Pe**********@discussions.microsoft.com> wrote:

Hi,

one of the main task of my currently developed application is to search in
small buffers for given patterns (average buffer size 1000 bytes). Now, for
some reasons I can't use the provided C std libs, so I need to implement my
own - but unfortunately I cannot find any hints about how to program such an
algorithm, so that it is really fast. Is there any (free) algorithm to start
with? Any free implementations?

Thanks a lot for any help
Peter

type "binary search" into google and press Search
you'll find the theory and example code, there is plenty of
information

Vin

[Carl Daniel [VC++ MVP]]

Peter Schmitz wrote:

Hi,

one of the main task of my currently developed application is to
search in small buffers for given patterns (average buffer size 1000
bytes). Now, for some reasons I can't use the provided C std libs, so
I need to implement my own - but unfortunately I cannot find any
hints about how to program such an algorithm, so that it is really
fast. Is there any (free) algorithm to start with? Any free
implementations?

http://www.nist.gov/dads/HTML/stringMatching.html
http://www-igm.univ-mlv.fr/~lecroq/string/

....list many searching algorithms. Which will be fastest in your
application depends on the size of the buffers, the size of the pattern to
be found, the number of partial matches, and various other factors.

-cd