Filtering sorted array with a defined threshold in python

Question

I have a sorted list, for example x = [120, 99, 90, 90, 40, 5, 5, 5, 1, 1]. I want to find the index of the last element that is greater than a variable, for example limit = 30. In this example, I want to get 4, because that's the index of 40 (and 5 is lower than 30). How can I do that efficiently in python? I can do looping like this:

def filtering(x, limit):
    for i,elem in enumerate(x):
       if elem <=limit:
          return i-1
    return i

But I was thinking if there is any better way / numpy function to do this. Thanks!

Will the array always be sorted? If yes, you can use binary search to this in O(log n) time instead of O(n) — Devesh Kumar Singh
– Devesh Kumar Singh, Commented Jul 8, 2021 at 14:10

Mustafa Aydın · Accepted Answer · 2021-07-08 14:32:02Z

Since you mentioned NumPy:

def last_ind(arr, limit):
    length = len(arr)
    sorter = np.arange(length)[::-1]
    pos = np.searchsorted(arr, limit, sorter=sorter)
    return length - pos - 1

Since searchsorted looks for an array sorted in ascending order but yours is sorted in descending order, we pass the indices of the list reversed to it with sorter. Also, searchsorted does the finding but it returns the index that you'd put the new number on; you, however, need the index of the previous element, hence -1. Lastly, since searchsorted worked as if it was sorted other way around, we correct the position by subtracting it from the length at the end.

Also, it returns -1 when no element in array is larger than the limit.

Sample runs:

>>> x
[120, 99, 90, 90, 40, 5, 5, 5, 1, 1]

>>> last_ind(x, 30)
4

>>> last_ind(x, 100)
0

>>> last_ind(x, 92)
1

>>> last_ind(x, 90)
3

>>> last_ind(x, 3)
7

>>> last_ind(x, 500)
-1

>>> last_ind(x, -51)
9

Le Huy Hoang · Accepted Answer · 2021-07-08 14:50:36Z

1

I would suggest to use numpy

>>> x = np.array([120, 99, 90, 90, 40, 5, 5, 5, 1, 1])
>>> np.where(x > 30)
(array([0, 1, 2, 3, 4]),)

The last returned element is the index you are looking for.

answered Jul 8, 2021 at 14:50

Le Huy Hoang

522 bronze badges

Collectives™ on Stack Overflow

Filtering sorted array with a defined threshold in python

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related