Linear Search | Algorithm

/ Algorithm / By

Linear Search is the easiest Search algorithm in computer science. If you ever try to search an element in a list sequentially, you already used a linear search algorithm. Congrats! You know already.

You may learn more details about the linear search by reading this article. It’s also known as sequential search and simple search.

In computer science, a linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched.

Wikipedia

Let’s see a visual example of a linear search.

Image Source: tutorialspoint

So, the concept is simple. Suppose we have a list with some random integer. We want to check if there is a specific element on that list. To do that, we can start check from the start of the list, going through the end of the list sequentially. If we find our searching element anywhere on the list, we will stop the search. Otherwise, we will stop the search when we reach the end of the list.

So let’s see the example below to see how to illustrate the concept in Python.

# Linear Search

lst = [1, 3, 10, 20, 5, 7, 15, 11, 9, 25]
num = int(input()) # 7

def linear_search(lst, num):
    for el in lst:
        if el == num:
            return True
            break
    return False

print(linear_search(lst, num)) # True

# print(linear_search(lst, 100)) # Return: False

First, we declare a random number list. Then we took an input for searching on the list. After that, we defined a function search. It takes two arguments. The first argument is a list and the second argument is an element.

I have declared a loop inside the function to check every element of the list from the beginning. Inside the loop, If the condition is true then we will return true. And the loop will stop here. Otherwise, the loop will continue its iteration until the end of the list.

If we can’t find our element in the whole list, false will return.

If we need the index of the element from this search, we can use range function. Let’s see how to do it.

# Linear Search
def linear_search(lst, num):
    for i in range(len(lst)):
        if lst[i] == num:
            return i
    return None

lst = [1, 3, 10, 20, 5, 7, 15, 11, 9, 25]

print(linear_search(lst, 10)) # 2
print(linear_search(lst, 100)) # None

If we find our element in the first index of a list, it will be the best-case scenario of this algorithm. The best time complexity of the linear search is O(1). If we don’t find an element in a list, it will be the worst-case scenario of this algorithm. The worst time complexity of the linear search is O(n). O(n) is also the average time complexity of this algorithm.

Though, this algorithm is not very efficient for searching. But it’s useful. Binary Search is an efficient searching algorithm and popular. I will try to cover Binary Search in a future article.

Related Posts

Scroll to Top