An Insight into the Numpy Searchsorted Function

Numpy is an abbreviation for Numerical Python. It is a python library used to work with multi-dimensional arrays and matrices. With the numpy library, we can incorporate several mathematical functions while using arrays. Moreover, with numpy, we can process arrays in python at a faster rate and perform scientific operations on it. Out of the many functions that the numpy library provides, today we shall talk about the numpy searchsorted function.

What is Numpy searchsorted?

Numpy Searchsorted is a function present in the numpy library of python used to deal with sorted arrays. The function is used to determine the index of an element while inserting it into a sorted array.

While inserting a new element into a sorted array, we would want the array to be sorted even after the insertion. So, the searchsorted function returns the index where the new element should be inserted to keep the array sorted.

If we assume that a given array ‘array’ is sorted and we want to insert a new element ‘e’, then it would be inserted such that:

array[ i - 1 ] < e < array[ i ]  (when we are checking from the left side of the array)

The searchsorted function would then return ‘i’ as the index of the new element ‘e‘, and the right-hand side element would be shifted by one bit.

Syntax of searchsorted

The syntax of numpy’s searchsorted function is:

numpy.searchsorted(a, v, side='left', sorter=None)

Parameters:

a: It is the input array of one dimension. Ideally, it should be sorted, especially if the value of the ‘sorter’ argument is ‘None’. It can be unsorted only if the ‘sorter’ contains an array containing indexes for sorting it.

v: It is the new value that has to be inserted into the array ‘a’. It can either be a single value or an array of elements.

side: It is an optional parameter whose value by default is ‘left’. Its value can be either ‘left’ or ‘right’. If its value is ‘left’, it will specify the first suitable index from the left side. Else, if its value is ‘right’, then it will specify the first suitable index from the right side of the array.

sorter: It is again an optional value that is set to ‘None’ by default. It is a one-dimensional array that has to be specified only if the array ‘a’ is unsorted. Then, it will contain the indexes which will sort the given array.

Return Value:

indices: The function searchsorted returns either a single index or an array of indexes at which the element(s) should be inserted.

Searchsorted for Binary Search

The searchsorted() function is used to perform a binary search. Binary search is an algorithm used to find the position of a given element from the list. A binary search is only applicable for a sorted list.

In binary search, we use the divide and conquer approach and then perform recursion. We calculate the middle of the array and then compare it with the value of the element which has to be found.

If it is less than the middle value, then the new list is from 0 to the middle value, and if not, then the new list is from the (middle + 1) value to the last element. We keep on dividing the list till the given element is found. The searchsorted() function serves the same purpose.

Examples of numpy searchsorted in python

We will be looking at some examples of scenarios where we will use the numpy searchsorted function in python.

Passing a single value for insertion

Let us first understand by using numpy searchsorted to insert a single element in the given array. First, we shall import the numpy function.

import numpy as np

Now we shall create a numpy array using the array() function present in the numpy library and save that array into a variable named ‘array’.

array = np.array([1,10,11,15,21])

Now, we shall use the searchsorted() function. We shall pass the array ‘array’ as the first argument and the value to be inserted, 17, as the second argument to the function. We shall save the returned index into a variable ‘i’.

i = np.searchsorted(array, 17)

On printing the variable ‘i’, the output is:

4

The reason is that the number ’17’ is greater than 15 and less than 21. So, it will be placed between 15 and 21, and hence the index is 4.

To insert element 17 into the array, we can make use of the insert() function. You need to pass the array, the element’s index, and the value to be inserted.

print(np.insert(array,4 ,17))

The output array after insertion is:

[ 1 10 11 15 17 21]

The entire code is:

import numpy as np

array = np.array([1,10,11,15,21])

i = np.searchsorted(array, 17)

print(i)

print(np.insert(array,4 ,17))

Passing multiple values for insertion

Instead of a single value, it is also possible to pass multiple values and receive an index for each value separately. We will pass an array of elements as the ‘v’ parameter.

Here, we will be inserting 5 elements into the given array [1, 10, 11, 15, 21].

i = np.searchsorted(array, [-7, -1, 20,3,30])

The output index will also be an array of indexes. If we print the variable ‘i’, the output will be:

[0 0 4 1 5]

Now, we can use the insert() method to insert multiple values by passing the array of indexes ‘i’ and the array of values. Note that the insert() method will not make any changes to the existing array, it will create a new array with the inserted values.

print(np.insert(array, [0, 0, 4, 1,5] ,[-7, -1, 20,3,30]))

The output array after insertion is:

[-7 -1  1  3 10 11 15 20 21 30]

The entire piece of code is:

import numpy as np

array = np.array([1,10,11,15,21])

i = np.searchsorted(array, [-7, -1, 20,3,30])

print(np.insert(array, [0, 0, 4, 1,5] ,[-7, -1, 20,3,30]))

Searching from right hand side

As mentioned before, by default the function searchsorted() will search from the left side. Searching from the left side means that it will specify the first suitable index from the left side.

The side will matter only in the cases where the element you are inserting is not unique and is already present in the list.

For example, let us consider two scenarios – one where we search from left and other when we search from right.

y = np.searchsorted([1,2,3,3,5,6], 3)

Here, we are trying to insert element ‘3’ into the given array. Since ‘side’ has not been mentioned, by default it will be considered as ‘left’. The first 3 it encounters from left is at the index position ‘2’ and so then it will place it between 2 and 3. So, it will assign the value 2 to y.

print(y)

Output:

2

But if we mention the parameter ‘side’ as ‘right’ explicitly, then the index value would be four because the first 3 it encounters from the right side that index position 3. So, it will place the element ‘3’ between 3 and 5 and give it an index of 4.

x = np.searchsorted([1,2,3,3,5,6], 3, side = 'right')

print(x)

Output:

4

The entire code for passing side as ‘right’ is:

import numpy as np

x = np.searchsorted([1,2,3,3,5,6], 3, side = 'right')

print(x)

Note, the resultant array will be same in both the cases after insertion, irrespective of the value of the ‘side’ parameter.

Searchsorted for string values

We can also use searchsorted for arrays containing string values.

print(np.searchsorted(['apple','vinegar','zucchini'], 'bananas'))

Here, the ‘grapes’ will be inserted at position 1. The output is:

1

Note that here the insertion will occur concerning the ascii values. Since the uppercase letters have a smaller ascii value than the lowercase letters, the answer would be different if we capitalize the ‘b’ in ‘bananas’.

print(np.searchsorted(['apple','vinegar','zucchini'], 'Bananas'))

The output is:

0

By capitalizing, the first letter ‘B’ will be placed at index 0.

Numpy searchsorted with 2D array

The numpy searchsorted function only accepts a one-dimensional array as an argument. If you will try to pass a multi-dimensional array, it will raise the error ‘object too deep for the desired array’.

But there are certain ways by which we can use the searchsorted() function on the two-dimension array. We can separately search for both the rows present in the two-dimensional array.

import numpy as np

a = [[1,2,6],[3,4,10]]

print(np.searchsorted(a[0], 2))

print(np.searchsorted(a[1], 10))

The output will be:

1
2

Else, we can also flatten the two dimensional array and then sort it before passing it into searchsorted().

import numpy as np

a = np.array([[1,2,6],[3,4,10]])

new = a.flatten()

new.sort()

print(new)

print(np.searchsorted(new, 9))

The output is:

[ 1  2  3  4  6 10]

5

FAQ’s on numpy searchsorted

That wraps up everything about the numpy searchsorted() function. If you have any questions in mind, feel free to let us know in the comments.

Until then, Keep Learning!