[Tutor] Searching Sorted Lists

R. Alan Monroe amonroe at columbus.rr.com
Sun Aug 21 17:06:28 CEST 2005


> DaSmith at technip.com wrote:
>> Hi, Can someone tell me if there is a bulit in Binary search function for
>> python lists ?
>> 
>> I am currently building lists and sorting them with a comparison function.
>> The only list search function I know is List.Index(X), which is pretty
>> inefficient I reckon, especially hen the lists are likely to contain 100's
>> or 100's of members.

> Hundreds or thousands of entries are pretty much nothing in computer 
> terms. Unless you have measured that it's a bottleneck in your 
> application, I wouldn't bother finding an alternative to index().

>  > Is there a search function that uses a compariosn function / binary 
> chop ?
>  > or will I have to implement my own ?

> It's quite easy to code it yourself if necessary. The Wikipedia has a 
> nice article on it, including sample code which looks very much like 
> Python: http://en.wikipedia.org/wiki/Binary_search

Can you use the built-in heapq module?

Alan



More information about the Tutor mailing list