[Tutor] binary vs. linear search
alan.gauld@bt.com
alan.gauld@bt.com
Mon, 26 Aug 2002 13:25:05 +0100
> The results for looking for 6,175 words in a list of 45,392 words are:
>
> binary: 3m 25s
> regular: 2m 58s
>
> I was surprised to find the binary search slower in this case. Can
> anyone explain why?
Binary search is good for finding 1 item in a sorted
list without scanning the entire list. But you are
looking for all items matching a certain criteria,
for that you need to dfo a scan so binary search
is unlikely to be effective. Even if you sorted by
word length first it would only be effective to use binary
search to find any single entry, not the whole block
of 6 char words. So far as the binary search is concerned
all of the 6 char words are the same so finding any of
them is good enough. You would need to keep searching
until there were none left. By contrast you can extract
them all in a single sweep without even sorting first...
As ever its a metter of selecting the most appropriate
tool for the task at hand.
Alan g.
Author of the 'Learning to Program' web site
http://www.freenetpages.co.uk/hp/alan.gauld
Alan g.