Re: Binary Search

On Tue, 19 Jun 2007 00:30:34 -0500, Rob Kennedy <me3@xxxxxxxxxxx>
wrote:

You do realize, of course, that it's just an implementation of what
Maarten, Dodi, and I suggested

The key word there was "suggested".
You (and others) suggested....whereas Stefan actually spent a few
minutes to give me something workable, rather than just theory or
pseudocode.


which you rejected on the grounds that
it "totally defeats the purpose of binary search" and "your performance
will suffer tremendously."

So what was your problem? Was it that this "hybrid" approach would be
too slow? Or was it just that your implementation didn't work?

My implementation worked fine, but performance does suffer
tremendously -- it takes a huge hit on an exponential scale as the
number of matches increases, which is why I was looking for something
else.

What I was hoping for was to avoid a sequential search altogether, and
somehow tweak the original binary search algorithm so that it's still
(more or less) a binary search as it scans the array. But because of
the "divide and conquer" approach of binary search, it became clear
pretty quickly that this wouldn't be simple or even possible.

A hybrid approach is obviously better than just plain sequential
search, but it's still nowhere close to ideal. Don't get me wrong
though -- SOME imrpovement is always better than no improvement. And
it's not that big of a deal if you have to wait 300 milliseconds for
your results...unless of course those 300 milliseconds are being
multiplied by a factor of "x" when you've got many such searches
taking place in parallel on a CPU with a finite amount of processing
power...in which case you want your results in 300 microseconds rather
than milliseconds.


As long as the number of duplicates is less than N - log N, the hybrid
search will go faster than a plain linear search. It's only when you
have *lots* of duplicates that a linear search will outperform this
hybrid search, and then only by a little bit. But that was never in
question (I hope).

A linear search would never outperform the hybrid. The very first hit
from the hybrid is a pure binary search, which is achieved in
microseconds...whereas in a linear search, the first hit could take
hundreds of times that amount because you're starting from element 1
and you have to work your way up to N before you have your results.

I've posted some benchmark test results a few hours ago, and never did
the linear search outperform (or even match) the hybrid's performance.
What did happen, however, was that as the number of matches grew, the
performance of the hybrid became more and more linear (which was to be
expected).


I'm not sure how to analyze the runtime of the pure-binary search
algorithm, but I'm convinced that it's no worse that O(log N).

Pure binary search is O(log(n)) at all times. Never worse, never
better. This is why the hybrid version can never outperform the
linear version, which is O(n) from start to finish.


The hybrid method is O(N) in the worst case.

Well...yeah....but that worst case is reached very very quickly
(immediately after the first result is returned). Once you've got
your first match, you immediately switch over to sequential search,
and the rest of the work is done in O(n) time.

Under ideal conditions, we would want to somehow skip all (or at least
most) of that sequential work in order to bring down the run times
drastically.
.

Relevant Pages

  • Re: Binary Search
    ... that this hybrid solution should be "slower" then additional recursive binary searches. ... Once you found a match using binary search, you KNOW that the neighbors of your match are potentionally additional matches. ... It's only when you have *lots* of duplicates that a linear search will outperform this hybrid search, and then only by a little bit. ...
    (comp.lang.pascal.delphi.misc)
  • Re: Search algorithm to use
    ... >binary search like the one I illustrated. ... and the simple linear search was only 25% slower than ... >less competent programmers, and because the myth of it being difficult ... >outperforms even the fully unrolled linear search. ...
    (comp.lang.c)
  • Re: Search algorithm to use
    ... > One comparison suffices if you use a sentinel. ... The linear search needs an increment. ... > binary search which is just about a wash. ... compare was "expensive" relative to other operations. ...
    (comp.lang.c)
  • Re: Binary Search
    ... That's fine for testing purposes, but out in the real world, you can't ... When I said I can't do it, I was referring to making the binary search ... perform the way I want (without introducing a linear search). ... with a working binary search that only needed 3 or 4 lines to be ...
    (comp.lang.pascal.delphi.misc)
  • binary search has a longer combinational delay than linear search
    ... I spent quite a lot of time building an HDL design that I thought ... elsif x<B1 then ... I assumed from my schooling that a binary search for the correct ... the linear search has a shorter combinational delay and therefore can ...
    (comp.lang.vhdl)