Linear Search implementation in Python [Data Structures & Algorithms]

This article deals with the linear search or sequential search algorithm. It’s a very simple search algorithm.

Linear Search

In the linear search algorithm:

• We start searching a list for a particular value from the first item in the list.
• We move from item to item from the first item to the last item in the list.
• If the desired item/value is found in the list then the position of that item in the list is returned/printed.
• If the desired item/value is not found in the list then we conclude that the desired item was not present in the list.

Implementation in Python

I have tried few different kinds of implementations. One is by using two different loops (for and while). The other difference is in the presentation of output. The core logic of the algorithm is the same.

Using While Loop

The output result will be the position of the searched element/item in the list. In programming, the counting of a list or array starts from 0. So, the first element of a list is said to be in 0th position. The second element of the list is said to be in the 1st position and so on.

In the below code, the number “4” is the third element of the list. So, it is said to be in the 2nd position of the list (as the list position counting starts from zero).

def linear_search(item_list, item):
    position = 0

    while position < len(item_list):
        if item_list[position] == item:
            return position
        else: 
            position = position + 1 

    return False

item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 4
print (linear_search(item_list, item))

# Output:
# 2

Using For Loop

The same implementation using For loop.

def linear_search(item_list, item):
    for key, value in enumerate(item_list):
        if value == item:
            return key

    return False


item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 44
print (linear_search(item_list, item))

#Output:
#6

Using For Loop & Printing some Message

def linear_search(item_list, item):     
    message = False

    for key, value in enumerate(item_list):
        if value == item:
            message = 'Element found in the list at location ' + str(key)
            break

    if not message:
        message = 'Element not found'   

    return message

    
item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 4
print (linear_search(item_list, item))

# Output:
# Element found in the list at location 2

Using For Loop & Printing some Message on Each Iteration

This is useful to see what’s going on inside the for loop.

def linear_search(item_list, item):     
    found = False

    for key, value in enumerate(item_list):
        print ('Position: %d, Value: %d, Searched Item: %d' % (key, value, item))
        if value == item:
            found = True
            print ('Element found in the list at location %d' % (key))
            break

    if not found:
        print ('Element not found')
    

    
item_list = [1, 2, 4, 8, 23, 25, 44, 78, 89, 100]
item = 44
linear_search(item_list, item)

# Output:
# Position: 0, Value: 1, Searched Item: 44
# Position: 1, Value: 2, Searched Item: 44
# Position: 2, Value: 4, Searched Item: 44
# Position: 3, Value: 8, Searched Item: 44
# Position: 4, Value: 23, Searched Item: 44
# Position: 5, Value: 25, Searched Item: 44
# Position: 6, Value: 44, Searched Item: 44
# Element found in the list at location 6

Time Complexity

Time taken by the linear search algorithm is at the comparison step where each item of the list is compared with the desired/searched item.

There can be two scenarios:

1. Searched item is found on the list

• Best case: Item found in the first comparison, i.e. searched item is the first element of the list
• Worst case: Item found in the last comparison, i.e. searched item is the last element of the list

In the example code above, there are 10 items on the list.

• Best case: Searching for 1 on the list, only 1 comparison is needed to find the number 1.
• Worst case: Searching for 100 in the list, 10 comparisons are required to find the number 100.

2. Searched item is not found on the list

• Best case and Worst case are the same
• All elements of the list should be compared to the searched item

In the example code above, there are 10 items on the list.

• Best case & Worst case: Searching for any number that is not on the list
• 10 comparisons are required to find the number that is not on the list

If there are n items on the list, then:

Big Oh Notation (O)

Measuring worst-case time complexity OR the longest possible time that an algorithm can take to complete.

As you can see in the above table, for linear search, the time complexity is O(n).

Hope this helps. Thanks.