To search for an element in a given data structure, we implement certain algorithms to efficiently carry out our tasks. These kinds of algorithms are known as Searching Algorithms. Some commonly used Searching Algorithms are – Linear Search Algorithm, Binary Search Algorithm, Jump Search Algorithm, Interpolation Search Algorithm, etc.
Out of all these algorithms, Linear Search Algorithm is the oldest and the simplest searching algorithm. In this article, we will be learning how Linear Search Algorithm is implemented on a data structure and also be looking into the Python 3 implementation of the algorithm.
Linear Search Algorithm is the first searching algorithm starters often learn when they start learning data structures and algorithms. Let us take an example and see how Linear Search Algorithm can be implemented.
Let us consider we have the following data in a Python List and we want to search for the value = 30.
0 1 2 3 4 5 6 7
- Step 1: We consider the first value, i.e. 21 from the list, and then compare that value with our search value, i.e. 30. Since it is not equal, we move on to the next value in the list.
- Step 2: Now, we consider the second element, i.e. 65, and compare it with value = 30. Since it is not equal, we again move on to the next element.
- Step 3: We have now 7 on our list. On comparing the two elements, we find 7 is not equal to 30. Hence, we move to the next element.
- Step 4: We have now element 30 on our list. We compare 30 with value = 30. Since 30 is equal to 30, we have found our desired element in the list. We can then print a message saying the element has been found and then return the index value = 3 of that element for further calculations.
As you can see, this is an iterative procedure, so this iteration will continue as long as the desired element is found or it reaches the end of the list. If it reaches the end of the list, but there is no such element found in the list, it can display a message saying, no such element is present.
So, this is the Linear Search Algorithm, and surely you must have found it out to be very simple.
- Worst Case – O(n) where n is the number of elements in a list. For the worst case, the element is at the end of the list, the loop needs to be executed for n times.
- Best Case – O(1). For the best case, the element is found in the first position in the list.
- Average Case – O(n). Summation of all the time taken for each element in the list and getting the average of all the elements in the list gives us O(n) time complexity.
Python 3 Implementation
Now let us look at how we can implement this algorithm in Python.
Now when we give input as 30, let us see the output:
If we enter a value that is not present in the list, for example, value = 980, let us see what the output is:
That is indeed the correct output as there is no 980 element present in the list.
Also Read: Data Scientist Salary in India
In this article, we have looked into what is a Linear Search Algorithm and also studied in detail how to search for a certain element from a list using the Linear Search Algorithm. Lastly, we also saw how we could practically implement the Linear Search Algorithm using Python 3 as a language and get our desired output.
If you are interested in Data Science, you must check out IIIT-B and upGrad’s PG Diploma in Data Science which has been carefully crafted for working professionals and offers numerous case studies, hands-on workshops, 1-on-1 mentorship, and much more.