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
.



Relevant Pages

  • RM 6.22 w/ A1000 on Solaris 2.6 w/ 36/72/144 Gb drives
    ... After several feedbacks and much www searching, the following scenario ... I am running Solaris 2.6. ...
    (comp.sys.sun.admin)
  • RE: changing the search sql
    ... If you are going to exclude some sites from searching, I'd suggest you can configure the portal for not searching these sites. ... "Managing Crawling of the Site Directory" in the SPS administrator guide. ... I am not clear about the scenario you have met. ...
    (microsoft.public.sharepoint.portalserver.development)
  • Re: Carb on Tecumseh engine leaking gas
    ... worst case scenario is just keep on searching ... on ebay and find one on there for cheap. ...
    (alt.home.repair)
  • rm command
    ... Here is scenario: ... I searching for specific files in a specific directory and then I want ... The following command is removing hundred ...
    (comp.unix.shell)
  • Search does not work after removing and reattaching sharepoint box from domain
    ... I had to remove a sharepoint box from one domain to another and the ... It indexes content but no searching results ... Reindexed both portal and non portal catalogues ... Has anyone been through this scenario?. ...
    (microsoft.public.sharepoint.portalserver)