Efficient way of counting number of elements smaller (larger) than cutoff in a sorted list
python
Solution
We can do even better with a binary search, which is handily implemented for us in the `bisect` module:
import bisect
n = bisect.bisect_left(lst, mx)
This takes time logarithmic in the length of `lst`, whereas a linear search with early termination is linear in `n`. This will generally be faster.
If you want to use a linear search, the `takewhile` function from `itertools` can stop the iteration early:
import itertools
n = sum(1 for _ in itertools.takewhile(lambda x: x < mx, lst))
Problem
Let's assume we have a sorted list: ``` lst = [1,3,4,89,456,543] # a long one ``` and what we'd like to do is to find the number of elements in a list which are smaller than, `mx`. Easy: ``` n = len([x for x in lst if x < mx]) ``` or with generator: ``` n = sum(1 for x in lst if x < mx) ``` I assume the second approach should be slightly quicker, but still, the problem here is that we are going through all the elements of a list while we could stop early. It doesn't use the fact that the list is sorted. Yep, I can do it with a loop: ``` s = 0 for x in lst: if x >= mx: break s += 1 ``` But, I have a feeling there must be a better (shorter and / or quicker) way to do the same thing, maybe with some generator or an external module function?