Linear Search

Linear Search

 

Linear search is a sequential searching algorithm that is we start from one end and check each element of the list until the desired element is found. It is the simple searching algorithm.

In Linearsearch, traverse the list completely and match every element of the list with the element whose location is to be found. If the match is found, then the location of item is returned; otherwise, the algorithm returns NULL.

The steps used in the implementation of LinearSearch are listed are given below –

    • Firstly, w traverse the array elements using a for loop.
    • In each iteration of for loop, compare the search element with the current array element
      • If  matches the element, then return the index of the corresponding array element.
      • If the element does not match, then move to the next element.
    • If there element no match and the search element is absent in the given array, return -1.

 

 

Algorithm

Linear_Search(a, n, val)  
Step 1: set pos = -1  
Step 2: set i = 1  
Step 3: repeat step 4 while i <= n  
Step 4: if a[i] == val  
set pos = i  
print pos  
go to step 6  
[end of if]  
set ii = i + 1  
[end of loop]  
Step 5: if pos = -1  
print "value is not present in the array "  
[end of if]  
Step 6: exit

Working of Linear search

suppose the elements of array are –

 

Linear Search Algorithm

 

 

Suppose the element to be searched is K = 41

Now, start from the first element and compare K with every element of the array.

 

 

Linear Search Algorithm

 

 

The value of K is41, is not matched with the first element of the array so, move to next element. And follow the same method until the respective element is found.

 

 

Linear Search Algorithm

 

 

 

The element to be searched is found. Hence, algorithm will return the index of the element matched.

 

 

Program for Linear search in C

#include <stdio.h>

int search(int array[], int n, int x) {
  
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}

Output

Element found at index: 3

 

Program for Linear search in C++

#include <iostream>
using namespace std;

int search(int array[], int n, int x) {

  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result;
}

Output

Element found at index: 3

Program for Linearsearch in Python

def linearSearch(array, n, x):

    for i in range(0, n):
        if (array[i] == x):
            return i
    return -1


array = [2, 4, 0, 1, 9]
x = 1
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
    print("Element not found")
else:
    print("Element found at index: ", result)

Output

Element found at index:  3

Program for Linear search in Java

class LinearSearch {
  public static int linearSearch(int array[], int x) {
  int n = array.length;

  for (int i = 0; i < n; i++) {
    if (array[i] == x)
    return i;
  }
  return -1;
  }

  public static void main(String args[]) {
  int array[] = { 2, 4, 0, 1, 9 };
  int x = 1;

  int result = linearSearch(array, x);

  if (result == -1)
    System.out.print("Element not found");
  else
    System.out.print("Element found at index: " + result);
  }
}

Output

Element found at index: 3

Linear Search complexity

 

1. Time Complexity

 

Case Time Complexity
Best Case O(1)
Average Case O(n)
Worst Case O(n)
  • Best Case Complexity – The best-case time complexity of linearsearch is O(1).
  • Average Case Complexity – The average case time complexity of linearsearch is O(n).
  • Worst Case Complexity – The worst-case time complexity of linearsearch is O(n).

 

The time complexity is O(n) .

 

2. Space Complexity

 

Space Complexity O(1)
  • The space complexity is O(1).

 

Read more, Shell sort

Share this post

Leave a Reply

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