Whither binary search?
sjmachin at lexicon.net
Tue Sep 26 23:21:45 CEST 2006
Fredrik Lundh wrote:
> Neil Cerutti wrote:
> >> bisect...
> > That doesn't tell me if an item doesn't exist in the sequence
> > though, does it? Maybe I'm being dense.
> I guess you could use something like
> import bisect
> def check(list, item):
> return list[bisect.bisect_left(list, item)] == item
> except IndexError:
> return False
> but unless your lists are really large, or your objects are expensive to
> compare, you could probably just use "in" instead.
> > My guess nobody keeps their sequences sorted in Python.
> well, people tend to use dictionaries when they need to look things up
... like those paper dictionaries with the words in alphabetical order
A common use case for looking things up in a sorted list is an
in-memory table of dates and rates (interest rates, insurance premium
rates, fee rates). In a big batch job, this sure beats doing "select
rate from table where ? between low_date and high_date" each time you
need a rate.
More information about the Python-list