Re: Binary Search
 From: John Dough <nobody@xxxxxxxxxxxxxxx>
 Date: Tue, 19 Jun 2007 00:10:13 0400
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
.
 FollowUps:
 Re: Binary Search
 From: Stefan Meisner
 Re: Binary Search
 References:
 Re: Binary Search
 From: Stefan Meisner
 Re: Binary Search
 From: John Dough
 Re: Binary Search
 From: Maarten Wiltink
 Re: Binary Search
 From: John Dough
 Re: Binary Search
 From: Maarten Wiltink
 Re: Binary Search
 From: John Dough
 Re: Binary Search
 From: John Dough
 Re: Binary Search
 From: Stefan Meisner
 Re: Binary Search
 From: John Dough
 Re: Binary Search
 From: Stefan Meisner
 Re: Binary Search
 Prev by Date: Re: Binary Search
 Next by Date: Re: Binary Search
 Previous by thread: Re: Binary Search
 Next by thread: Re: Binary Search
 Index(es):
Relevant Pages
