[Tutor] Searching Sorted Lists

[Danny Yoo]

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


Hi Daniel,

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:

   http://www.python.org/doc/lib/module-bisect.html

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!