Linear Search in Python

Linear Search is the most simple search algorithm.

Considering you have a data structure, we have to go through each and every element of the data structure until we find the element we want.

The implementation for a linear search below takes two arguments, array, which is the collection we are going to iterate over, and value, which is them item whose index we want to locate.

Then we use a for loop to go through every item in the array by using the range() function which will return from 0 until the length of the array.

For every item, the if statement checks if the current ith item of the array corresponds to the value we are looking for.

It will then return the index i of the array if there is match.

def linear_search(array, value):
    for i in range(len(array)):
        if array[i] == value:
            return i

To test our linear search implementation, we are going to use the code below.

It initializes an array with 4 strings.

Then we pass the array and the value ‘book’ as arguments for the linear_search(array, value) function.

Finally we check if the variable index is empty, if it is we print ‘Value not found’, if it is not empty we print the index found by our function.

array = ['soap', 'rice', 'book', 'beer']

index = linear_search(array, 'book')

if index:
    print(f'Found at index {index}')
else:
    print('Value not found')

Found at index 2

Efficiency

This simple search algorithm is also known as "Brute Force".

Since we are simply going through every single item, there is nothing very clever about it.

If we were looking for ‘soap’ instead of ‘book’ in our example, the algorithm would be lightning fast since it would return the first element of the list.

Now, consider a list with 1 million items and the element we are looking for is the last one, now we need to iterate though all the array to find the item what we want, which is not very good in terms of efficiency.

So, considering the worst-case scenario of efficiency, we have an algorithm complexity of O(n) for the Linear Search.