flopscope.

flopscope.numpy.searchsorted

fnp.searchsorted(a, v, side='left', sorter=None)[flopscope source][numpy source]

Find indices where elements should be inserted to maintain order.

Adapted from NumPy docs np.searchsorted

Areacore
Typecustom
NumPy Refnp.searchsorted
Cost
per-operation
Flopscope Context

Binary search; cost = m*ceil(log2(n)).

Find the indices into a sorted array a such that, if the corresponding elements in v were inserted before the indices, the order of a would be preserved.

Assuming that a is sorted:

table




side

returned index i satisfies

left

a[i-1] < v <= a[i]

right

a[i-1] <= v < a[i]

Parameters

a:1-D array_like

Input array. If sorter is None, then it must be sorted in ascending order, otherwise sorter must be an array of indices that sort it.

v:array_like

Values to insert into a.

side:{'left', 'right'}, optional

If 'left', the index of the first suitable location found is given. If 'right', return the last such index. If there is no suitable index, return either 0 or N (where N is the length of a).

sorter:1-D array_like, optional

Optional array of integer indices that sort array a into ascending order. They are typically the result of argsort.

Returns

indices:int or array of ints

Array of insertion points with the same shape as v, or an integer if v is a scalar.

See also

Notes

Binary search is used to find the required insertion points.

As of NumPy 1.4.0 searchsorted works with real/complex arrays containing nan values. The enhanced sort order is documented in sort.

This function uses the same algorithm as the builtin python bisect.bisect_left (side='left') and bisect.bisect_right (side='right') functions, which is also vectorized in the v argument.

Examples

>>> import flopscope.numpy as fnp
>>> flops.searchsorted([11,12,13,14,15], 13)
2
>>> flops.searchsorted([11,12,13,14,15], 13, side='right')
3
>>> flops.searchsorted([11,12,13,14,15], [-10, 20, 12, 13])
array([0, 5, 1, 2])

When sorter is used, the returned indices refer to the sorted array of a and not a itself:

>>> a = flops.array([40, 10, 20, 30])
>>> sorter = flops.argsort(a)
>>> sorter
array([1, 2, 3, 0])  # Indices that would sort the array 'a'
>>> result = flops.searchsorted(a, 25, sorter=sorter)
>>> result
2
>>> a[sorter[result]]
30  # The element at index 2 of the sorted array is 30.