Linear Search or Sequential Search

Linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.

Problem: You are given an array arr[] of size n consisting of integers, write a function to search a given element x in arr[].

A simple approach is to do linear search, i.e

1. start from the leftmost element of arr[] and one by one compare x with each element of arr[].
2. If x matches an element then return an index.
3. otherwise return -1.

Example: Consider the following image:

Linear search code:

package com.walking.techie.data.structure.search;


public class LinearSearch {

  // This function will reaturn the index of element  in arr[]
  public static int search(int arr[], int n, int x) {

    for (int i = 0; i < n; i++) {
      // Return an index of element if the element is found in array
      if (arr[i] == x) {
        return i;
      }
    }
    // Come here means element is x is not found in array
    // Return -1 if the given element x is not found
    return -1;
  }


  public static void main(String[] args) {
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 7;
    int position = LinearSearch.search(arr, arr.length, x);
    if (position != -1) {
      System.out.println("Element " + x + " found at position " + position);
    } else {
      System.out.println("Element not found.");
    }
  }
}

Complexity:

• Time complexity of linear search is O(n).
• Auxiliary Space complexity is O(1).

Recursive implementation of Linear Search

Recursive Linear search code:

package com.walking.techie.data.structure.search;

public class RecursiveLinearSearch {

  // Recursive linear search method to find element x in array
  public static int recSearch(int arr[], int left, int right, int x) {
    // Return -1 when element x is not in array
    if (right < left) {
      return -1;
    }

    // return index when element x is present in array.
    if (arr[left] == x) {
      return left;
    }
    return recSearch(arr, left + 1, right, x);
  }

  public static void main(String[] args) {
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 7;
    int position = RecursiveLinearSearch.recSearch(arr, 0, arr.length - 1, x);
    if (position != -1) {
      System.out.println("Element " + x + " found at position " + position);
    } else {
      System.out.println("Element not found.");
    }
  }
}

Complexity:

• Time complexity of linear search is O(n).
• Auxiliary Space complexity is O(n) when we consider method call stack.

Linear search is rarely used practically because of other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching comparision to linear search.