Re: Binary Search

John Dough wrote:
On Mon, 18 Jun 2007 23:57:25 +0200, "Stefan Meisner"
<stefan.meisner@xxxxxxx> wrote:
Attached is the code which uses the "hybrid" solution. And for me it is not reasonable, 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. So there's no need to search. You can just go up and down the list and compare for additional matches. The next element do match or it does not. If it does not, you just leave the loop.
Of course you should add the upper/lower bounds (which I have hardcoded) as parameters. But it's only a sample ;)

Thank you very much for the code. I appreciate it greatly.

I've tried it, and it works perfectly.

You do realize, of course, that it's just an implementation of what Maarten, Dodi, and I suggested, 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?

It actually looks very similar
to what I came up with, but the main difference is that you were using
some very simple for-loops with breaks, and I was using repeat loops.
I didn't do any timing analysis yet, but just from looking at the
code, it looks like your method will be faster than mine just from the
way it is structured.

But what I'm really interested in now is to blow up the array to
something like 100,000 or 1 million elements...fill it with some
random data and then I want to see how fast the hybrid search is
compared to just a sequential search.

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).

The question is whether the hybrid search will outperform an exclusively binary search. I've posted such a search method in another response.

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). The hybrid method is O(N) in the worst case.

--
Rob
.