Re: Binary Search



On Tue, 19 Jun 2007 02:30:15 +0200, "Stefan Meisner"
<stefan.meisner@xxxxxxx> wrote:

You are welcome!
And please let me know. I'm pretty sure, that using a binary search
to find the initial match and then continuing with just a simple linear
collection of the remaining matches is a viable solution.

It's actually a lot faster than what I had imagined at first.
The key, of course, is that it all depends on the number of items
found.

The more items that are found, the more time there will be spent in
the linear section of the algorithm which runs in O(n) time. But even
with that factored in, it's still much faster than a regular
sequential search on average.

Here are some numbers...

I've created an array with 1 million random strings...and ran 4
different test scenarios:

Scenario One: No matches will be found
Scenario Two: 1% will match
Scenario Three: 50% will match
Scenario Four: 99% will match

Test results are as follows:

Scenario #1
Searching for "test":
No matches found
-----------------------------
Hybrid --- 0.00737 milliseconds (7.37 microseconds)
Sequential --- 264.887 milliseconds



Scenario #2:
Searching for "test":
10347 matches found (1%)
-----------------------------
Hybrid --- 2.679 milliseconds
Sequential --- 264.303 milliseconds



Scenario #3:
Searching for "test":
505409 matches found (50%)
-----------------------------
Hybrid --- 129.072 milliseconds
Sequential --- 285.752 milliseconds



Scenario #4:
Searching for "test":
989865 matches found (99%)
-----------------------------
Hybrid --- 251.982 milliseconds
Sequential --- 305.876 milliseconds
.