Hacker News Reader

Comment by paskozdilar | Hacker News Reader

> Where's the one liner for that in python? O wait, there isn't one.

Here it is:

    >>> import bisect
    >>> sorted_fruits = ['apple', 'banana', 'orange', 'plum']
    >>> bisect.bisect_left(sorted_fruits, 'banana')
    1

View on HN

Note that that finds the index to the left of the insertion point for the value given, but doesn’t perform a containment test; you have to also check that the index is in the list (instead of off the end) and that the value at the resulting index equals the value of interest to test containment. Which can be a one-liner without redundant calls (with walrus), but is a bit ugly.

(Of course, for a custom class you can just wrap it in a __contains__ method and then just use the “in” operator.)

> you have to also check that the index is in the list (instead of off the end) and that the value at the resulting index equals the value of interest to test containment

True. However, the hardest part of the binary search algorithm is implemented through bisect, so it still saves a lot of developer time.

How about a more complex type? Something like a custom class instance?

As long as your type is isomorphic to an array, you can implement __len__() and __getitem__(i) and bisect will still work:

    >>> class C:
    ...     def __len__(self):
    ...             return 10
    ...     def __getitem__(self, i):
    ...             if i >= 10:
    ...                     raise IndexError('out of range')
    ...             return i+1
    ... 
    >>> c = C()
    >>> import bisect
    >>> bisect.bisect_left(c, 1)
    0
    >>> bisect.bisect_left(c, 4)
    3

Thanks!

Or you can implement a binary search in your type's __contains__ and just use `"foo" in c`

You can do that too, using the bisect, provided you have the __len__ and __getitem__ implemented:

    class C:
        def __len__(self): ...
        def __getitem__(self, i): ...
        def __contains__(self, x):
            i = bisect.bisect_left(self, x)
            return i < len(self) and self[i] == x

At that point it's just syntactic sugar.

That looks like three lines to me.

The first two lines are setup, real code would already have done that.

You could maybe count the import, but you'd have to do that once and could do multiple bisections, so it's amortized.

Setting the variable doesn't count because you do, of course, need a variable to perform an operation on a variable. Sorting the array also wouldn't count because you can't use binary search if the array isn't sorted.

Reply on news.ycombinator.com