andrea andrea - 1 month ago 5
Python Question

Find if a sorted array of floats contains numbers in a certain range efficiently

I have a sorted numpy array of floats, and I want to know whether this array contains number in a given range. Note that I'm not interested in the positions of the number in the array. I only want to know if there is at least one number that falls in the range.

Since I have to do the very same operation on a large numbers of intervals (the array remains constant during the entire operation), I'm concerned about the efficiency.

Can anyone help me?

Answer

As talked about in the comments, np.searchsorted could be useful and indeed it is. As stated in the question, the array stays the same, while we have different ranges across iterations. So, let's say the ranges are stored in a (n,2) shaped array, such that the first column represents the start, while the second column are the stop values of those ranges.

We would have a solution with np.searchsorted, like so -

np.searchsorted(a,ranges[:,0]) != np.searchsorted(a,ranges[:,1])

The idea is that if there's any number within a range, then the sorted indices found using the first column (start values) would be lesser than and thus not equal to the indices from the second column (stop values).

Sample run -

In [75]: a   # Input data array
Out[75]: 
array([ 13.,  20.,  22.,  24.,  36.,  50.,  52.,  60.,  64.,  65.,  65.,
        66.,  72.,  76.,  81.,  84.,  88.,  88.,  90.,  97.])

In [76]: ranges # Array of ranges
Out[76]: 
array([[ 19.,  26.],
       [ 22.,  33.],
       [ 25.,  35.],
       [ 38.,  62.]])

In [77]: np.searchsorted(a,ranges[:,0]) != np.searchsorted(a,ranges[:,1])
Out[77]: array([ True,  True, False,  True], dtype=bool)
Comments