DS / Algo Latest

Linear Search

274 views 22/02/2022 admin 0 Comments Algorithm of linear search, Linear Search, Linear Search complexity, Program for Linear search in C, Program for Linear search in Java, Program for Linear search in Python, Space Complexity of linear search, Time Complexity of linear search, Working of 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 –

Suppose the element to be searched is K = 41

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

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.

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).

Linear Search

Algorithm

Working of Linear search

Program for Linear search in C

Output

Program for Linear search in C++

Output

Program for Linearsearch in Python

Output

Program for Linear search in Java

Output

Linear Search complexity

1. Time Complexity

2. Space Complexity

Share this:

You May Also Like

Leave a Reply Cancel reply