236

I have a 1D array in numpy and I want to find the position of the index where a value exceeds the value in numpy array.

E.g.

aa = range(-10,10)

Find position in aa where, the value 5 gets exceeded.

2
  • 3
    One should be clear whether there could be no solution (since eg the argmax answer will not work in that case ( max of (0,0,0,0) = 0) as ambrus commented
    – seanv507
    Commented Jul 3, 2015 at 11:42
  • 1
    I agree with that and I have included an answer below (even though there's an accepted answer which I think is still ambiguous). I think correctness in a code is more important than just performance. Commented Aug 12, 2021 at 19:54

8 Answers 8

307

This is a little faster (and looks nicer)

np.argmax(aa>5)

Since argmax will stop at the first True ("In case of multiple occurrences of the maximum values, the indices corresponding to the first occurrence are returned.") and doesn't save another list.

In [2]: N = 10000

In [3]: aa = np.arange(-N,N)

In [4]: timeit np.argmax(aa>N/2)
100000 loops, best of 3: 52.3 us per loop

In [5]: timeit np.where(aa>N/2)[0][0]
10000 loops, best of 3: 141 us per loop

In [6]: timeit np.nonzero(aa>N/2)[0][0]
10000 loops, best of 3: 142 us per loop
10
  • 173
    Just a word of caution: if there's no True value in its input array, np.argmax will happily return 0 (which is not what you want in this case).
    – ambrus
    Commented Feb 7, 2014 at 13:15
  • 20
    The results are correct, but I find the explanation a bit suspicious. argmax does not seem to stop at the first True. (This can be tested by creating boolean arrays with a single True at different positions.) The speed is probably explained by the fact that argmax does not need to create an output list.
    – DrV
    Commented Oct 8, 2014 at 14:11
  • 2
    I think you're right, @DrV. My explanation was meant to be about why it gives the correct result despite the original intent not actually seeking a maximum, not why it is faster as I cannot claim to understand the inner details of argmax.
    – askewchan
    Commented Oct 8, 2014 at 14:24
  • 8
    @DrV, I just ran argmax on 10 million-element Boolean arrays with a single True at different positions using NumPy 1.11.2, and the position of the True mattered. So 1.11.2's argmax seems to "short-circuit" on Boolean arrays. Commented Sep 4, 2017 at 22:12
  • 7
    I repeated @UlrichStern's experiment with an array of 2^30 elements (prefilling each with ones then with zeros then adding a single true value to eliminate blank page trickery, page fault noise, etc). np.argmax was 1e5 times faster when the only true element was at the beginning of the array instead of the end. This was with numpy 1.16.5.
    – Mr Fooz
    Commented Apr 23, 2020 at 18:27
132

given the sorted content of your array, there is an even faster method: searchsorted.

import time
N = 10000
aa = np.arange(-N,N)
%timeit np.searchsorted(aa, N/2)+1
%timeit np.argmax(aa>N/2)
%timeit np.where(aa>N/2)[0][0]
%timeit np.nonzero(aa>N/2)[0][0]

# Output
100000 loops, best of 3: 5.97 µs per loop
10000 loops, best of 3: 46.3 µs per loop
10000 loops, best of 3: 154 µs per loop
10000 loops, best of 3: 154 µs per loop
4
  • 32
    This is really the best answer assuming the array is sorted (which isn't actually specified in the question). You can avoid the awkward +1 with np.searchsorted(..., side='right')
    – askewchan
    Commented Oct 8, 2014 at 14:58
  • 3
    I think the side argument only makes a difference if there are repeated values in the sorted array. It doesn't change the meaning of the returned index, which is always the index you could insert the query value at, shifting all the following entries to the right, and maintain a sorted array.
    – Gus
    Commented Mar 9, 2015 at 4:07
  • 2
    @Gus, side has an effect when the same value is in both the sorted and the inserted array, regardless of repeated values in either. Repeated values in the sorted array just exaggerate the effect (the difference between the sides is the number of times the value being inserted appears in the sorted array). side does change the meaning of the returned index, though it does not change the resulting array from inserting the values into the sorted array at those indices. A subtle but important distinction; in fact this answer gives the wrong index if N/2 is not in aa.
    – askewchan
    Commented Feb 11, 2017 at 1:19
  • 1
    As hinted at in the above comment, this answer is off by one if N/2 is not in aa. The correct form would be np.searchsorted(aa, N/2, side='right') (without the +1). Both forms give the same index otherwise. Consider the test case of N being odd (and N/2.0 to force float if using python 2).
    – askewchan
    Commented Feb 11, 2017 at 1:25
44

I was also interested in this and I've compared all the suggested answers with perfplot. (Disclaimer: I'm the author of perfplot.)

If you know that the array you're looking through is already sorted, then

numpy.searchsorted(a, alpha)

is for you. It's O(log(n)) operation, i.e., the speed hardly depends on the size of the array. You can't get faster than that.

If you don't know anything about your array, you're not going wrong with

numpy.argmax(a > alpha)

Already sorted:

enter image description here

Unsorted:

enter image description here

Code to reproduce the plot:

import numpy
import perfplot


alpha = 0.5
numpy.random.seed(0)


def argmax(data):
    return numpy.argmax(data > alpha)


def where(data):
    return numpy.where(data > alpha)[0][0]


def nonzero(data):
    return numpy.nonzero(data > alpha)[0][0]


def searchsorted(data):
    return numpy.searchsorted(data, alpha)


perfplot.save(
    "out.png",
    # setup=numpy.random.rand,
    setup=lambda n: numpy.sort(numpy.random.rand(n)),
    kernels=[argmax, where, nonzero, searchsorted],
    n_range=[2 ** k for k in range(2, 23)],
    xlabel="len(array)",
)
5
  • 4
    np.searchsorted isn't constant-time. It's actually O(log(n)). But your test case actually benchmarks the best-case of searchsorted (which is O(1)).
    – MSeifert
    Commented Apr 19, 2018 at 19:22
  • @MSeifert What kind of input array/alpha do you need to see O(log(n))? Commented Apr 19, 2018 at 19:38
  • 1
    Getting the item at index sqrt(length) did lead to very bad performance. I also wrote an answer here including that benchmark.
    – MSeifert
    Commented Apr 19, 2018 at 19:59
  • I doubt searchsorted (or any algorithm) can beat the O(log(n)) of a binary search for sorted uniformly distributed data. EDIT: searchsorted is a binary search. Commented Nov 27, 2018 at 5:59
  • If you knew the uniform distribution you could beat binary search with O(1). If I have monotonic numbers between 0 - 1000 and you want to find value 748 you can go to position 784. This is a sorted uniformly distributed set of data, and an algorithm that can beat that.
    – Tatarize
    Commented Apr 26, 2021 at 18:09
19
In [34]: a=np.arange(-10,10)

In [35]: a
Out[35]:
array([-10,  -9,  -8,  -7,  -6,  -5,  -4,  -3,  -2,  -1,   0,   1,   2,
         3,   4,   5,   6,   7,   8,   9])

In [36]: np.where(a>5)
Out[36]: (array([16, 17, 18, 19]),)

In [37]: np.where(a>5)[0][0]
Out[37]: 16
17

Arrays that have a constant step between elements

In case of a range or any other linearly increasing array you can simply calculate the index programmatically, no need to actually iterate over the array at all:

def first_index_calculate_range_like(val, arr):
    if len(arr) == 0:
        raise ValueError('no value greater than {}'.format(val))
    elif len(arr) == 1:
        if arr[0] > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    first_value = arr[0]
    step = arr[1] - first_value
    # For linearly decreasing arrays or constant arrays we only need to check
    # the first element, because if that does not satisfy the condition
    # no other element will.
    if step <= 0:
        if first_value > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    calculated_position = (val - first_value) / step

    if calculated_position < 0:
        return 0
    elif calculated_position > len(arr) - 1:
        raise ValueError('no value greater than {}'.format(val))

    return int(calculated_position) + 1

One could probably improve that a bit. I have made sure it works correctly for a few sample arrays and values but that doesn't mean there couldn't be mistakes in there, especially considering that it uses floats...

>>> import numpy as np
>>> first_index_calculate_range_like(5, np.arange(-10, 10))
16
>>> np.arange(-10, 10)[16]  # double check
6

>>> first_index_calculate_range_like(4.8, np.arange(-10, 10))
15

Given that it can calculate the position without any iteration it will be constant time (O(1)) and can probably beat all other mentioned approaches. However it requires a constant step in the array, otherwise it will produce wrong results.

General solution using numba

A more general approach would be using a numba function:

@nb.njit
def first_index_numba(val, arr):
    for idx in range(len(arr)):
        if arr[idx] > val:
            return idx
    return -1

That will work for any array but it has to iterate over the array, so in the average case it will be O(n):

>>> first_index_numba(4.8, np.arange(-10, 10))
15
>>> first_index_numba(5, np.arange(-10, 10))
16

Benchmark

Even though Nico Schlömer already provided some benchmarks I thought it might be useful to include my new solutions and to test for different "values".

The test setup:

import numpy as np
import math
import numba as nb

def first_index_using_argmax(val, arr):
    return np.argmax(arr > val)

def first_index_using_where(val, arr):
    return np.where(arr > val)[0][0]

def first_index_using_nonzero(val, arr):
    return np.nonzero(arr > val)[0][0]

def first_index_using_searchsorted(val, arr):
    return np.searchsorted(arr, val) + 1

def first_index_using_min(val, arr):
    return np.min(np.where(arr > val))

def first_index_calculate_range_like(val, arr):
    if len(arr) == 0:
        raise ValueError('empty array')
    elif len(arr) == 1:
        if arr[0] > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    first_value = arr[0]
    step = arr[1] - first_value
    if step <= 0:
        if first_value > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    calculated_position = (val - first_value) / step

    if calculated_position < 0:
        return 0
    elif calculated_position > len(arr) - 1:
        raise ValueError('no value greater than {}'.format(val))

    return int(calculated_position) + 1

@nb.njit
def first_index_numba(val, arr):
    for idx in range(len(arr)):
        if arr[idx] > val:
            return idx
    return -1

funcs = [
    first_index_using_argmax, 
    first_index_using_min, 
    first_index_using_nonzero,
    first_index_calculate_range_like, 
    first_index_numba, 
    first_index_using_searchsorted, 
    first_index_using_where
]

from simple_benchmark import benchmark, MultiArgument

and the plots were generated using:

%matplotlib notebook
b.plot()

item is at the beginning

b = benchmark(
    funcs,
    {2**i: MultiArgument([0, np.arange(2**i)]) for i in range(2, 20)},
    argument_name="array size")

enter image description here

The numba function performs best followed by the calculate-function and the searchsorted function. The other solutions perform much worse.

item is at the end

b = benchmark(
    funcs,
    {2**i: MultiArgument([2**i-2, np.arange(2**i)]) for i in range(2, 20)},
    argument_name="array size")

enter image description here

For small arrays the numba function performs amazingly fast, however for bigger arrays it's outperformed by the calculate-function and the searchsorted function.

item is at sqrt(len)

b = benchmark(
    funcs,
    {2**i: MultiArgument([np.sqrt(2**i), np.arange(2**i)]) for i in range(2, 20)},
    argument_name="array size")

enter image description here

This is more interesting. Again numba and the calculate function perform great, however this is actually triggering the worst case of searchsorted which really doesn't work well in this case.

Comparison of the functions when no value satisfies the condition

Another interesting point is how these function behave if there is no value whose index should be returned:

arr = np.ones(100)
value = 2

for func in funcs:
    print(func.__name__)
    try:
        print('-->', func(value, arr))
    except Exception as e:
        print('-->', e)

With this result:

first_index_using_argmax
--> 0
first_index_using_min
--> zero-size array to reduction operation minimum which has no identity
first_index_using_nonzero
--> index 0 is out of bounds for axis 0 with size 0
first_index_calculate_range_like
--> no value greater than 2
first_index_numba
--> -1
first_index_using_searchsorted
--> 101
first_index_using_where
--> index 0 is out of bounds for axis 0 with size 0

Searchsorted, argmax, and numba simply return a wrong value. However searchsorted and numba return an index that is not a valid index for the array.

The functions where, min, nonzero and calculate throw an exception. However only the exception for calculate actually says anything helpful.

That means one actually has to wrap these calls in an appropriate wrapper function that catches exceptions or invalid return values and handle appropriately, at least if you aren't sure if the value could be in the array.


Note: The calculate and searchsorted options only work in special conditions. The "calculate" function requires a constant step and the searchsorted requires the array to be sorted. So these could be useful in the right circumstances but aren't general solutions for this problem. In case you're dealing with sorted Python lists you might want to take a look at the bisect module instead of using Numpys searchsorted.

6

I'd like to propose

np.min(np.append(np.where(aa>5)[0],np.inf))

This will return the smallest index where the condition is met, while returning infinity if the condition is never met (and where returns an empty array).

4

You should use np.where instead of np.argmax. The latter will return position 0 even if no value is found, which is not the indexes you expect.

>>> aa = np.array(range(-10,10))
>>> print(aa)
array([-10,  -9,  -8,  -7,  -6,  -5,  -4,  -3,  -2,  -1,   0,   1,   2,
         3,   4,   5,   6,   7,   8,   9])

If the condition is met, it returns an array of the indexes.

>>> idx = np.where(aa > 5)[0]
>>> print(idx)
array([16, 17, 18, 19], dtype=int64)

Otherwise, if not met, it returns an empty array.

>>> not_found = len(np.where(aa > 20)[0])
>>> print(not_found)
array([], dtype=int64)

The point against argmax for this case is: the simpler the best, IF the solution is not ambiguous. So, to check if something fell into the condition, just do a if len(np.where(aa > value_to_search)[0]) > 0.

1

I would go with

i = np.min(np.where(V >= x))

where V is vector (1d array), x is the value and i is the resulting index.

1
  • This solution is slower than np.where(capacity < demand)[0][0]. There is no reason to use this except readability of np.min. Commented Aug 17, 2022 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.