# 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

.

**Follow-Ups**:**Re: Binary Search***From:*Stefan Meisner

**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

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