Home » Data Structures & Algorithms, Python15 January 2018

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).

Using For Loop

The same implementation using For loop.

Using For Loop & Printing some Message

Using For Loop & Printing some Message on Each Iteration

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

Time Complexity

Time taken by 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 in 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 same
– All elements of the list should be compared to the searched item

In the example code above, there are 10 items in 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:

CasesWorst CaseBest CaseAverage Case
searched item is present in the list1nn/2
searched item is not present in the listnnn

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.

Python

Get New Post by Email

Find me on

FacebookTwitterGoogle+LinkedInRSS Feed

Comments are closed.