[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?
More information about the Tutor