Linear Search in Data Structure

Free Data Structures and Algorithms courses with real-time projects Start Now!!

Let us consider a scenario where you have to find a book in your personal stack of books. Assuming that the stack is not arranged in any order, the only way to find a book is to read the title of each book. And when you find the desired book you stop this process and don’t look into further books. This is a real-life example of linear search.

Linear Search

Linear search is the most basic search algorithm in the data structure. It is used to search any element in a linear data structure like arrays and linked lists. Linear Search algorithm compares the search element to each element of the Data Structure and returns the location of the element if found.

Method to use Linear Search

1. Start from the first element and compare each element with the search element.
2. If the element is found, return at which position element was found.
3. If the element is not found, return -1.

Algorithm for Linear Search

Steps for Linear search are as follows:

Linear_Search ( Array A [ n ], search_element x)

1: Set i to 1

2: if i > n then go to step 7

3: if A[i] = x then go to step 6

4: assign i+1 to i

5: Go to Step 2

6: Print Element x Found at index i and exit

7: display “element not found”

Pseudocode for Linear Search

procedure linear_search (array, value)

   for each item in the array
      if item == value
         return the item's index
      end if
   end for

end procedure

Example of Linear Search

Input Array: {‘D’,’A’,’T’,’A’,’F’,’L’,’A’,’I’,’R’}

Search Element: ‘I”

linear search

Output:

‘I’ is present at index 7

Linear Search Implementation in C++

#include <iostream>
using namespace std;
 
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
 
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
   
    int  result = search(arr, n, x);
    if (result == -1)
        cout << "Element is not present in array"
    else
        cout << "Element found at location " << result+1;
    return 0;
}

Implementation of Linear Search in C

#include <stdio.h>
 
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
 
 
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
   
    
    int result = search(arr, n, x);
    if(result == -1)
        printf("Element is not present in array")
    Else
        printf("Element is present at index %d", result);
    return 0;
}

Linear Search Implementation in Java

class DataFlair
{
    public static int search(int arr[], int x)
    {
        int n = arr.length;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }
 
   
public static void main(String args[])
    {
        int arr[] = { 2, 3, 4, 10, 40 };
        int x = 10;
 
        
        int result = search(arr, x);
        if (result == -1)
            System.out.print(
                "Element is not present in array");
        else
            System.out.print("Element is present at index "
                             + result);
    }

Implementation of Linear Search in Python

def search(arr, n, x):
 
    for i in range(0, n):
        if (arr[i] == x):
            return i
    return -1
 
arr = [2, 3, 4, 10, 40]
x = 10
n = len(arr)
 
result = search(arr, n, x)
if(result == -1):
    print("Element is not present in array")
else:
    print("Element is present at index", result)



Time Complexity of Linear Search

The worst-case time complexity of a linear search algorithm is O(n) since it compares the search element to all the elements in an array or linked list. 

Due to this reason, linear search is not common since other algorithms like binary search and hash table perform search operations at a very fast rate.

ComplexityBest CaseAverage CaseWorst Case
Time ComplexityO(1)O(n)O(n)
Space complexityO(1)

Conclusion

In this article, we witnessed the most basic searching technique used for small inputs. Linear search is used for small inputs sizes. We have some more efficient algorithms for large inputs that we will study in future articles.

The time complexity of the linear search algorithm for the worst case is very non-efficient and therefore is not used widely in the professional world.

You give me 15 seconds I promise you best tutorials
Please share your happy experience on Google

follow dataflair on YouTube

Leave a Reply

Your email address will not be published. Required fields are marked *