# searching a list of tuples

John Machin sjmachin at lexicon.net
Thu Feb 14 17:41:13 EST 2002

```"Jason Orendorff" <jason at jorendorff.com> wrote in message news:<mailman.1013636242.28850.python-list at python.org>...
> Marcus Stojek writes:
> > I have a (huge) list of tuples :
> > list=(float 1,float 2,float 3,int).
> >
> > The list has been sorted with list.sort()
> > Now I have to slice the list in a way
> > that:
> >
> >   a <= float 1 <= b
>
> Well, on my computer I can make a float that
> represents "infinity".  So this works:
>
> import bisect
>
> INF = 1e600
> left = bisect.bisect_right(mylist, (a, -INF, -INF, -INF))
> right = bisect.bisect_left(mylist, (b, INF, INF, INF))
> myslice = mylist[left:right]
>

Couple of problems here:

(1) As you said, "on my computer". This trick does not work on all
platforms for floats, and cannot be extended to types (like integer)
that don't have a representation of "infinity". Pax Knuth, but cute
algorithms that depend on sentinels that "can't appear in the data"
are a PITA.

(2) The OP has misunderstood [see his post requesting help with
optimisation] and is calling bisect* with an actual data value as the
second arg; result: lossage if that data value actually appears in the
list. The OP wanted
a <= alist[i] <= b.

>>> alist = [10, 20, 30, 30, 30, 40]
>>> import bisect
>>> def slicer(srtdlist, lowval, highval):
...    lowinx = bisect.bisect_right(srtdlist, lowval)
...    highinx = bisect.bisect_left(srtdlist, highval)
...    return srtdlist[lowinx:highinx]
...
>>> slicer(alist, 0, 10)
[]
>>> slicer(alist, 0-1, 10+1)
[10]
>>> slicer(alist, 20-1, 30+1)
[20, 30, 30, 30]
>>> slicer(alist, 20, 30+1)
[30, 30, 30]

```