3 ms·

> 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', '

> 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

rad_gruchalski 4y ago
How about a more complex type? Something like a custom class instance?
- paskozdilar 4y ago
  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
  - rad_gruchalski 4y ago
    Thanks!
  - faho 4y ago
    Or you can implement a binary search in your type's __contains__ and just use `"foo" in c`
    - paskozdilar 4y ago
      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.
dragonwriter 4y ago
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.)
- paskozdilar 4y ago
  > 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.
mellavora 4y ago
That looks like three lines to me.
- faho 4y ago
  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.

rad_gruchalski 4y ago

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

paskozdilar 4y ago
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
- rad_gruchalski 4y ago
  Thanks!
- faho 4y ago
  Or you can implement a binary search in your type's __contains__ and just use `"foo" in c`
  - paskozdilar 4y ago
    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.

dragonwriter 4y ago

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

paskozdilar 4y ago
> 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.

mellavora 4y ago

That looks like three lines to me.

faho 4y ago
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.