Linear Search

Linear Search is the process of finding an item from a collection of elements. Linear search is also known as Sequential Search, because the elements are searched in the sequential order until the searched item is found.

As name suggests, Linear Search applies to Linear Data Structures like Arrays and Linked Lists. Average and Worst case performance of Linear Search Algorithms are denoted as O_(n). Time complexity of a Linear Search algorithm is directly proportional to the number of inputs and is indicated by a diagonal line as shown in the chart below.

There are many search algorithms of Logarithmic Time Complexity which perform much better compared to Linear Search Algorithms, especially when the data collection is huge.

Linear Search Uses

Practical use cases of Linear Search Algorithms are limited to smaller data sets. Its simplicity in implementation makes it particularly useful for students to develop small scale applications. It can also be helpful for beginners to start with the basics of DSA.

A single for loop is enough to implement this algorithm. Whereas faster algorithms that uses concepts like Divide and Conquer requires data to be sorted before performing the search. So scenarios that uses smaller data collections or data sets that gets updated dynamically during the run time most probably will work better if Linear Search is used.
Performance Comparison

Let us compare the performance of linear search with another search algorithm that follows a divide and conquer approach. Below are two gif images showing how an item is searched using Linear Search and much more efficient Binary Search Algorithm.

In Linear Search, nodes are searched sequentially till the searched item is found. As the data collection becomes larger, its efficiency decreases.

Binary Search is a divide and conquer method, that has higher efficiency for larger sets of data, making this suitable for many practical scenarios.

As you can see, faster algorithms like Binary Search require the data to be kept sorted and this may be an additional overhead for insert, update or delete operations.

Code Samples

Below are few sample code implementations of Linear Search Algorithm in some of the most common programming languages.

arry = [5, 12, 15, 18, 40, 30, 22, 45, 8, 34]

find = 40
pos = -1

for i in range(len(arry)):
    if(arry[i] == find):
        pos = i
        break

if(pos > -1):
    print("Element found at position : ", pos)
else:
    print("Element not found")

class LinearSearch   
{
    public static void main(String[] args)   
    {  
        int arry[] = {5, 12, 15, 18, 40, 30, 22, 45, 8, 34};
        int find = 40;
        int pos = -1;

        for (int i = 0; i < arry.length; i++) {
            if (arry[i] == find) {
                pos = i;
                break;
            }
        }

        if(pos > -1)
            System.out.println("Element found at position : " + pos);
        else
            System.out.println("Element not found");
    }
}

using System;
using System.Threading;

namespace DSA
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arry = { 5, 12, 15, 18, 40, 30, 22, 45, 8, 34 };
            int find = 40;
            int pos = -1;

            for (int i = 0; i < arry.Length; i++)
            {
                if (arry[i] == find)
                {
                    pos = i;
                    break;
                }
            }

            if (pos > -1)
                Console.WriteLine("Element found at position : " + pos);
            else
                Console.WriteLine("Element not found");

            Thread.Sleep(5000);
        }
    }
}

function linearSearch(find) {
    var arry = [5, 12, 15, 18, 40, 30, 22, 45, 8, 34];
    var pos = -1;

    for (let i = 0; i < arry.length; i++) {
        if (arry[i] == find) {
            pos = i;
            break;
        }
    }

    if(pos > -1)
        alert("Element found at position : " + pos);
    else
        alert("Element not found");
}

f = 40;
linearSearch(f);

Linear Search

Linear Search Uses

Performance Comparison

Code Samples