Hello everyone, today we will learn linear search in python. So basically Linear Search Python tutorial will deal the concept of linear search, it’s algorithm, example and so on.But before going forward we have to understand the logic behind search. so let’s see what they are?
What Is Searching – A Quick Overview
Searching is a most prevalent task that we do in our everyday life. Like searching phone numbers in contact list, searching student roll number in student’s information and many more. searching also play an important role in measuring the performance of any app or website. But now the question is that what is the meaning of searching?
- Searching is a technique that helps in finding the position of a given element or value in a list.
- If we find the element which we are searching then we will say searching is successful but we don’t found the element then we will say searching is not successful.
Types Of Searching
There are mainly two types of searching –
- This is the simplest searching technique.
- It sequentially checks each element of the list for the target searching value until a match is found or until all the elements have been searched.
- This searching technique can be performed on both type of list, either the list is sorted or unsorted.
- It is the fastest searching technique.
- It is based on the Divide and Conquer method.
- But in this technique the elements of list must be in sorted order.
- Binary search begins by comparing the middle element of the list with the searching value.
- If the searching value matches the middle element, its position in the list is returned.
- And If the searching value is less than the middle element, the search continues in the lower half of the list.
- If the searching value is greater than the middle element, the search continues in the upper half of the list. By doing this, the algorithm eliminates the half in which the searching value cannot lie in each iteration.
Linear Search Python – Search Element Sequentially
- It is also known as sequential search.
- In this search technique, we start at the beginning of the list and search for the searching element by examining each subsequent element until the searching element is found or the list is exhausted.
- It is one of the simplest searching technique.
- This technique can be applied to both sorted and unsorted list.
- Time Complexity : θ ( n )
- Space Complexity : O(1)
Linear Search Example
Let us take an example where linear search is applied –
- If you are asked to find the name of the person having phone number say “1234” with the help of a telephone directory.
- Since telephone directory is sorted by names not by numbers so we have to go each and every number of the directory.
There are many example where linear search applied but i am taking only one here.
Linear Search Advantages
- It is simplest and conventional searching technique.
- Linear search can be applied on both sorted or unsorted list of data.
- It is easy to implement.
Linear Search Disadvantages
- If the list have large numbers of data then it is insufficient for searching data.
- It takes more time for searching data.
- If there is 200 elements in the list and you want to search element at the position 199 then you have to search the entire list, that’s consume time.
Algorithm Of Linear Search
Now we will see it’s algorithm. It’s algorithm is very simple as you can see below.
Linear Search ( List A, Item x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
How Linear Search Works ?
Now we will consider an example to understand the mechanism of linear search.
- In this example we take an unsorted list which have 7 elements.
- Now we have to find the element 15 that is our target element.
- Now we will see how the searching is happening.
- First of all, in first comparison we will compare target element with the element present at first place.If both will match then we will return element found but in this example element is not found at first place so we will move to the second comparison.
- In second comparison we will repeat the same procedure as we have done earlier.
- We will repeat this process until we find the target element.
- In this example we find the target element in 5th comparison. Now we will stop the searching process and return the target element.
- The above process is depicted in this figure very clearly.
Also Read: Python Threading Example for Beginners
Linear Search Implementation
Now we will learn how to implement linear search in python. To implement linear search we have to write the code as given below.
for i in range(len(myList)):
myList = [1,7,6,5,8]
print("Element in List :", myList)
x = int(input("enter searching element :"))
result = linear_search(myList,x)
print("Element not found in the list")
print( "Element " + str(x) + " is found at position %d" %(result))
- First of all we have to define a function. Let’s give it name linear_search(). It takes two arguments, first one is our list and another one is the item which is to be searched.
- Then start a for loop, inside this loop we will compare the searching element with the element of current position. If both elements will match then we return the current position of searching element. If the element will not found in the list then we will return -1 that means element is not found.
- Now we will define our list, in this list i am taking just 5 elements but you can take as your wish.
- Then print the list of element in the screen. It is not necessary but you can do it if you like.
- Now take the input from the user what they want to search.
- And finally call the method linear_search() which we have already defined.
- And now we will check whether searching element is found in the list or not.
- For this, if result == -1 then we will print element is not found in the list otherwise we will print the current position of the searching element.
Finally the simple code is completed and now its time to run the code. On running the code user will be asked to enter the searching element, just enter the element and the output will be as follows –
So friends this was all about Linear Search Python tutorial. I hope you have learned lots of things about linear search. If you have any doubt regarding this then feel free to comment. Please share it with your friends that will help them learning python very well. Thanks every one.