Linear Search

In this tutorial, you will learn about linear search. Also, you will find working examples of linear search in C, C++, Java and Python.

Linear search is the simplest search algorithm and often called sequential search. In this type of searching, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match is found then location of the item is returned otherwise the algorithm returns NULL.

Linear Search Algorithm

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

Linear Search Programming Examples

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;
}

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);
  }
}

Linear Search Complexities

Time Complexity = O(n)

Space Complexity = O(1)

Linear Search Applications

It is used when the array elements are unordered and the number of search queries is very less.
It is used when there are only a few elements in the array.

See also :

Jump Search
Binary Search
Interpolation Search
Exponential Search