The linear search algorithm searches each element in an array sequentially. If the search key does not match an element in the array, the algorithm informs the user that the search key is not present. If the search key is in the array, the algorithm tests each element until it finds one that matches the search key and returns the index of that element.

As an example, consider an array containing the following values:

35 73 90 65 23 86 43 81 34 58

and a program that’s searching for 86. The linear search algorithm first checks whether 35 matches the search key. It does not, so the algorithm checks whether 73 matches the search key. The program continues moving through the array sequentially, testing 90, then 65, then 23. When the program tests 86, which matches the search key, the program returns the index 5, which is the location of 86 in the array. If, after checking every array element, the program determines that the search key does not match any element in the array, it returns a sentinel value (e.g., -1).

Let’s define a function linear_search for performing linear searches of an array of integers. The function receives as parameters the array to search (data) and the search_key. The for loop iterates through data’s elements and compares each with search_key. If the values are equal, linear_search returns the index of the matching element. If there are duplicate values in the array, the linear search returns the index of the first element that matches the search key. If the loop ends without finding the value, the function returns -1.

In [1]: def linear_search(data, search_key):
   ...:     for index, value in enumerate(data)::
   ...:         if value == search_key:
   ...:             return index
   ...:     return -1
   ...:
   ...:

To test the function, let’s create an array of 10 random integers in the range 10–90:

In [2]: import numpy as np

In [3]: np.random.seed(11)

In [4]: values = np.random.randint(10, 91, 10)

In [5]: values
Out[5]: array([35, 73, 90, 65, 23, 86, 43, 81, 34, 58])

The following snippets call linear_search with the values 23 (found at index 4), 61 (not found) and 34 (found at index 8):

In [6]: linear_search(values, 23)
Out[6]: 4

In [7]: linear_search(values, 61)
Out[7]: -1

In [8]: linear_search(values, 34)
Out[8]: 8