[Tutor] binary vs. linear search

[alan.gauld@bt.com]

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