What is Linear Search algorithm? Easy to understand

Searching is the process of selecting particular information from a collection of data. That collection can be anything from numbers in a phone book or pages with certain words when you search for something in a search engine. Search is usually done on a key. A key is a unique value used to identify a single item.

Linear search is the process of finding a key/item in a sequence. The term linear means that we have to look at all the elements, even if the item is not in the list.

what is linear search algorithm?

Linear literally means “progressing from one stage to another in a single series of steps”. So, in linear search algorithm, we will start from the first element, till the last element. We will look at every element to see if it matches with our target element, if so, we will return True, else we will return False.

Use of ‘in’ operator:

if key in list:
    print("The key is in the list")
else:
    print("The key is not in the list")

The in operator checks the entire list one by one, if it finds the key, it returns True, else it returns False. IN makes the code easier to understand, but it hides the implementation of Linear Search algorithm.

Consider the 1D array in above figure. To determine if number 11 is in the list, we begin the search with checking the first element at index 0. Since, the first element doesn’t contain 11, we move to the next element, i.e., 5, and so on until we find 11 at index 4.

Now suppose we want to check if number 19 is in the list. We will begin the search by looking at the element in the first index. Since the first element doesn’t contain 19, we will move to the next element and repeat until we have checked every element in the list. Our algorithm will traverse the entire list, before returning False, because number 19 is not in the list.

Linear Search Algorithm Python code

1   def LinearSearch(values, target):
2       n = len(values)
3    
4       for i in range(n):
5           if values[i] == target:
6               return True
7       return False
8
9  values = [1,19,21,2,17,55,73,100,25,6]
10 print(LinearSearch(values, 73))

Explanation:

• In line #1, we defined our Linear Search Algorithm function with two attributes. First is the list or collection of items to search, and second is the target, which we want to find if it is in the list or not.
• In the 2nd line, we calculated the length of our list using the python’s len() function.
• In the 4th line, we used a For-Loop to loop through entire list to search our target. We have used n variable, which we defined in the 2nd line to calculate the number of items.
• Our For-loop start checking the first element of the list (i.e., 1), matches it with the target (i.e.,73). returns False as they are not equal and move on to the next element. Now, the element (i.e., 19) is matched with target (i.e., 73), and as before returns False, because both of these aren’t equal to each other.
• The Linear Search Algorithm keeps on moving until it finds 73 in the list. At that time, it returns True and program exits the loops.

Time complexity of Linear Search

Since the Linear Search Algorithm traverses the entire list to find the target element, the worst-case time complexity of the aforementioned algorithm is O(n). Which simply means that the algorithm will check the entire list, even if the target element is not in the list.

Summary

Linear search is the basic searching algorithm. It’s not very efficient as it has to look for every element in the list, but it is good starting point. Everyone must know how this works and what is the time complexity.