Linear Search in Python
Searching is a method for determining whether a specific element is contained in the provided list or not. Linear Search and Binary Search are two different forms of searches.Both methods are frequently used to find a specific element in the provided list.
What is linear Search in Python?
To efficiently complete our tasks, we employ certain algorithms to search for an element in a given data structure. Searching algorithms is another name for such algorithms. Linear search algorithms, binary search algorithms, interpolation search algorithms, jump search algorithms, etc. are a few examples of frequently used search algorithms.
Linear search in Python is one way to find items in a list. A sequential manner is used to find the requested element. Every element is checked about the value we're seeking. If both are equal, the element is found, and the process returns that element's index position.
Let's get a general idea of how linear search in Python operates:
- Start with the first element in the list and go through the list checking the key with each element.
- The index position of the element is returned if an element value is found equal to that of a key.
- The return value is null if the element isn't found.
How to perform Linear Search in Python?
Now let's understand the proper working of the linear search in python with an example.
Suppose a list of elements is given and let's say we want to look for the value 29 in that list. The list of elements is given below.
Step by step explanation of the example is given below.
Step 1: We take into account the first value, which is 20 from the list, and compare it to our search value, which is 29. We move on to the following value in the list because it is not equal.
Step 2: Next, we take into account the second element which is 64, and compare it with our required value of 0. We proceed to the following element once more because it is not equal.
Step 3: Now we have 6 as the next element in the list. When we compare the two elements, we see that 6 is not equivalent to 29. We now go on to the next element.
Step 4: Now have got 29 as our next element. So this 29 is compared to our required 29 and we have identified the element we were looking for in the list since 29 is equivalent to 29. The element's index value is 3 now this index value can be returned for use in further calculations after we print a message indicating that the element has been located at index 3.
This is an iterative process that you can see, so this iteration will continue until the desired element is identified or it hits the end of the list. When it is reached the end of the list but no matching element is there, it can show a message informing the user that such an item is not present in the given list. So this is an algorithm for linear search in Python, which you must have found to be pretty simple.
Use Cases of Linear Search
- One can use linear search when the array size is not too big or its constant, its easier/faster to implement thus saves development time.
- This alogrithm is easy to understand and apply so this can be used by developers to search an element over the small size array.
Python Linear Search Algorithm
We currently have a basic idea of how linear search in Python works. For a better understanding, let's look at the algorithm followed by the code:
- Create the linear search() function.
- Declare the array, array length, and value to be found as three parameters.
- Initialize the for a loop.
- Compare the value of the key with each element as you iterate.
- Return index if the element is present.
- else return element is absent.
Python Program for Linear Search
Now let's dive into the programming part of this linear search in Python.
An example given below is for searching the index of 6 in the given array if it is present.
Now as you can see in the above example that we need 6 to be searched in the given array whether it is present there or not. So the function starts searching for 6 from 1st element of the list and finally it found out the element 6 at index 2, so the function will return the statement that "Element is at index 2".
An example given below is for searching the index of 9 in the given array if it is present.
Now as you can see in the above example that we need 9 to be searched in the given array whether it is present there or not. So the function starts searching for 9 from 1st element of the list and after traversing over the list till the last element the 9 was not found. So the function will return the statement Element Not Found.
An example given below is for searching the index of 2 in the given array if it is present.
Now as you can see in the above example that we need 2 to be searched in the given array whether it is present there or not. So the function start searching for 2 from the 1st element of the list and finally after traversing the whole list it was found at the last index which is 4, so the function will return the statement that "Element is at index 4".
Q. What is the time complexity for performing a linear search in Python, over an array?
A. The linear search algorithm's time complexity is:
- For base case it is
- For average case it is
- For worst case it is
Since the linear search technique checks each element to find out the desired number, it is suited for smaller lists (less than 100). If there are 10,000 elements in the list and the required element is at the very end, it will take a long time to compare it to each one. The binary search technique can be used to quickly obtain results.
Q. What is the space complexity for performing a linear search in Python, over an array?
A. As no extra space or auxiliary is used during the whole searching process of linear search so the space complexity for performing the linear search will be .
- Sequential search is another name given for linear search.
- Linear search in Python is much more time taking in comparison with the binary search if an element is present at the last index.
- Linear search in Python is suitable for searching in small arrays.