In this tutorial, you will learn about the linear search. Likewise, you will discover working instances of linearsearch C, C++, Java, and Python.

What is Linear Search?

A LinearSearch is the most fundamental type of searching algorithm. A LinearSearch consecutively travels through your assortment (or data structure) searching for a coordinating value. All in all, it looks down a list, one item at a time, without jumping.

Consider it a method of finding your way in a phonebook. A LinearSearch is beginning toward the start, reading each name until you find what you’re searching for. n complexity terms this is an O(n) search – the time taken to search the list gets bigger at a similar rate as the list does.

Linear search is the least difficult searching algorithm that searches for an element in a list in consecutive order. We start toward one side and check each element until the desired element isn’t found.


How Linear Search Works?

The accompanying steps are followed to search for an element k = 1 in the list underneath.

  1. Start from the primary element, compare k and every element x

2. On the off chance that x == k, return the index.

3. Else, return not found.


Linear Search Algorithm

LinearSearch(array, key)
  for each item in the array
    if item == value
      return its index

Python, Java, and C/C++ Examples

Python

# Linear Search in Python


def linearSearch(array, n, x):

    # Going through array sequencially
    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)

Java

// Linear Search in Java

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

  // Going through array sequencially
  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);
  }
}

C

// Linear Search in C

#include <stdio.h>

int search(int array[], int n, int x) {
  
  // Going through array sequencially
  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);
}

C++

// Linear Search in C++

#include <iostream>
using namespace std;

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

  // Going through array sequencially
  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;
}

LinearSearch Complexities

Time Complexity: O(n)

Space Complexity: O(1)


LinearSearch Applications

  1. For searching operations in smaller arrays (<100 items).

Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.