[Tutor] Searching Sorted Lists
dyoo at hkn.eecs.berkeley.edu
Fri Aug 19 21:33:09 CEST 2005
> 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.
Out of curiosity, why are you sorting the lists? Just wondering --- it
may be that a sorted list is the appropriate data structure for your
problem, but perhaps another might be better suited.
There is a binary search method in the 'bisect' module:
It doesn't appear to take in a customized comparison, but it shouldn't be
too hard to modify it so that it does. I'd recommend taking the source to
bisect_left, and work from there.
Best of wishes to you!
More information about the Tutor