FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!

searching unsorted lists in Python




In terms of efficiency, in Python and other languages that use a box and pointer system of lists, generally:

if you are given an unsorted list, and only want to search it once, just go ahead and search through until you find the item.

If you wish to search multiple times, sort and use binary.

To sort a list, the Big O efficiency is n.logn

To search a list in linear, that would n

So:

for a once off search, sort and binary is n.logn + logn compared to linear search n, linear search wins.

for multiple searches, sort and binary is n.logn + k.logn compared to linear k.n

Obviously then, if you are given a sorted list, go for binary as a general rule.



0 blog comments below




FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.