Linear Search algorithm


This is the search algorithm that will never fail in our Universe.

Linear search (also, known as sequential search) is an algorithm 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. This is one of the most basic search algorithms and is directly, inspired by real-life events.

Algorithm

Steps involved in this algorithm are:

  • Step 1: Select the first element as the current element.
  • Step 2: Compare the current element with the target element. If matches, then go to step 5.
  • Step 3: If there is a next element, then set current element to next element and go to Step 2.
  • Step 4: Target element not found. Go to Step 6.
  • Step 5: Target element found and return location.
  • Step 6: Exit process.

Complexity

  • Worst case time complexity: O(N)
  • Average case time complexity: O(N)
  • Best case time complexity: O(1)
  • Space complexity: O(1)

In theory, Linear search in average makes n/2 comparisons where n is the number of elements in the set. At the most, linear search algorithm takes n comparisons.

In terms of implementation, linear search algorithm takes 2n+1 comparisons (n to check if target element is found and n+1 comparisons to check if end of list is reached) in the worst case. With optimizations, we can make n+1 comparisons in the worst case.

Visual run

linear_search

Implementations

Implementation of Linear search algorithm in 17 languages that includes C, C++, Java, C#, Clojure, Go, Haskell, JavaScript, Kotlin, Meta, Nim, PHP, Ruby, Rust, Scala and Swift.

  • C
  • C++
  • Java
  • C#
  • Clojure
  • Go
  • Haskel
  • JavaScript
  • Kotlin
  • Meta
  • Nim
  • PHP
  • Python
  • Ruby
  • Rust
  • Scala
  • Swift

C


    #include <stdio.h>
    /*
     * Part of Cosmos by OpenGenus Foundation
     * Input: an integer array with size in index 0, the element to be searched
     * Output: if found, returns the index of the element else -1
    */
    int search(int arr[], int size, int x)
    {
        int i=0;
        for (i=0; i<size; i++)
            if (arr[i] == x)
                return i;
        return -1;
    }    
    int main() 
    {
        int arr[] = {2,3,1,5}; // Index 0 stores the size of the array (initially 0)
        int size = sizeof(arr)/sizeof(arr[0]);
        int find = 1;
        printf("Position of %d is %d\n", find, search(arr,size,find));
        return 0;
    }

C++


  /*
     * Part of Cosmos by OpenGenus Foundation
     * Author: Visakh S
     * Github: visakhsuku
     * Input: The number of elements in an array, The element to be searched, An integer array.
     * Output: if found returns "found" else "not found", using the sentinel linear search algorithm.
    */
    #include <iostream>
    #include <vector>
    using namespace std;
    void sentinelLinearSearch(std::vector<int> v,int n,int x)
    {
        int last,i=0;
        last=v[n-1];
        v[n-1]=x;
        while(v[i]!=x)
            i++;
        if(i<n-1||last==x)
            cout<<"found";
        else
            cout<<"not found";
    }
    int main()
    {
        ios_base::sync_with_stdio(false);cin.tie(NULL);
        int n,x,input;
        std::vector<int> v;
        cin>>n>>x;
        for (int i = 0; i < n; ++i)
        {
            cin>>input;
            v.push_back(input);
        }
        sentinelLinearSearch(v,n,x);
        return 0;
    }

Java


// Part of Cosmos by OpenGenus Foundation
import java.util.Scanner;
/**
 * The {@code LinearSearch} class is the simplest of the searching
 * algorithm. The goal of the algorithm is to check the existence of an
 * element in the given array.
 * How it works
 * {@code LinearSearch} goes through each element of the given array until
 * either the element to be searched is found or we have reached the end
 * of the array.
 * Complexity
 * Time Complexity -> O(n)
 * Space Complexity -> O(1) *
 * @author Cosmos by OpenGenus Foundation
 */
class LinearSearch {    
    /*
     * Searches for key in the given array. Returns the index within this
     * array that is the element searched for.
     * @param   arr
     *          Array that is the source of the search.
     * @param   key
     *          The number to be searched for in the array.
     * @return  the index of the element, else -1.
     */  
    static int linearSearch(int arr[], int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key)
                return i;
        }
        return -1;
    }
    /*
     * A recursive implementation of {@link #linearSearch()}
     * @param   arr
     *          Array that is the source of the search.
     * @param   key
     *          The number to be searched for in the array.
     * @return A recursive call to {@link #recursiveLinearSearch()}
     */
    static int recursiveLinearSearch(int arr[], int key) {
        return recursiveLinearSearch(arr, key, 0);
    }
    private static int recursiveLinearSearch(int arr[], int key, int index) {
        // Key not found at all.
        if (index == arr.length)
            return -1;        
        // Key found at current index.
        if (key == arr[index])
            return index;        
        // Else, keep moving through indices
        return recursiveLinearSearch(arr, key, index + 1);
    }    
    public static void main(String args[]) {
        // Object of scanner class to take input.
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter the size of the array to be searched");
        int size = sc.nextInt();
        int arr[] = new int[size];        
        // Loop to take input.
        for(int i = 0; i < size; i++) {
            System.out.println("Enter the element number " + (i + 1) + " of the array");
            arr[i] = sc.nextInt();
        }        
        System.out.println("Enter the number you want to find");
        int key = sc.nextInt();        
        System.out.println("Position of " + key + " is " + linearSearch(arr, key));
        System.out.println("Position of " + key + " is " + recursiveLinearSearch(arr, key));
    }
}

Tab 4


  // Part of Cosmos by OpenGenus
    public class LinearSearch
    {
        public static void Main(string[] args)
        {
            int[] items = new int[] { 10, 12, 52, 634, 24, 743, 234, 7, 25, 742, 76, 25};
        int itemToFind = 634;
        int itemIndex = linearSearch(items, itemToFind);
        if(itemIndex != -1)
            System.Console.WriteLine(itemToFind + " found at " + itemIndex);
        else
            System.Console.WriteLine(itemToFind + " not found!");
    }

    public static int linearSearch(int[] items, int itemToFind)
    {
        for(int i = 0; i < items.Length; i++)
        {
            if(items[i] == itemToFind)
            {
                return i;
            }
        }
        return -1;
    }
}


  ; generally in list processing languages we
    ; we don't work with indices but just in case
    ; you wanted to find position of element from list head
    (defn linear-search-list
          "Returns the position of the list element from head"
          ([tlist elem]                                         ;tlist is a linked list
            (linear-search tlist elem 0))
          ([[x remm] elem idx]
            (if (= x elem)
              idx
              (recur remm elem (inc idx)))))                    ;recursive call with remaining list & args
(defn linear-search-in-vec
      "Function takes persistent vector and searches for elem"
      ([tvec elem]
        (linear-search-in-vec tvec elem idx))
      ([tvec elem idx]
        (if (= elem (get tvec idx))
          idx
          (recur tvec elem (inc idx)))))

;Example usage
(linear-search (list 1 2 3 4 5) 4)
(linear-search-in-vec (vector 1 2 3 4 5 6) 4)


  package main
    import (
        "fmt"
    )
func main() {
    arr := []int{1, 3, 45, 56, 8, 21, 7, 69, 12}
    find := 56
    index := search(arr, find)
    if index != -1 {
        fmt.Printf("%d found at index %d", find, index)
    } else {
        fmt.Printf("%d not found!", find)
    }

}

func search(arr []int, x int) int {
    for i, n := range arr {
        if n == x {
            return i
        }
    }
    return -1
}


    linearsearch :: (Eq a) => [a] -> a -> Maybe Int
    linearsearch [] _ = Nothing
    linearsearch (x:xs) y = if x == y then Just 0 else (1 +) <$> linearsearch xs y
  

  /*
     * Part of Cosmos by OpenGenus Foundation
     * Input    :   An integer array and the element to be searched
     * Output   :   If found returns the index of element or else -1
     * Example  :
     *              var index = linearSearch([1, 2, 3, 4, 7, 8], 8);
     * 
    */
    function linearSearch(arr, element) {
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] === element) {
                return i;
            }
        }
        return -1;
    }
  

  // Part of Cosmos by OpenGenus Foundation
fun <T> linearSearch(array: Array<T>, key: T): Int? {
    for (i in 0 until array.size) {
        if (array[i] == key) {
            return i
        }
    }
    return null
}

fun main(args: Array<String>) {
    val sample: Array<Int> = arrayOf(13, 17, 19, 23, 29, 31, 37, 41, 43)
    val key = 23

    val result = linearSearch(sample, key)

    println(when (result) {
        null -> "$key is not in sample"
        else -> "Position of $key is $result"
    })
}


  (* Part of Cosmos by OpenGenus Foundation *)
let rec linear_search x = function
  | [] -> -1
  | hd :: tl when hd == x -> 0
  | hd :: tl -> 1 + (linear_search x tl);;


  proc linear_search[T](collection: seq[T], item: T): T =
    for i in 0..(collection.len() - 1):
        if collection[i] == item:
            return i
    return -1
let s = @[42, 393, 273, 1239, 32]
echo linear_search(s, 273) # prints "2"
echo linear_search(s, 32)  # prints "4"
echo linear_search(s, 1)   # prints "-1"


  echo sprintf("Position of %d is %d\n", $search = 33, linearSearch($array = [7, 11, 13, 33, 66], $search));


    '''
    Part of Cosmos by OpenGenus Foundation
    '''
    def linear_search(arr, x):
        for i in range(len(arr)):
            if arr[i] == x:
                return i
        return -1
    arr = []
    while True:
        inp = raw_input("Enter a number (non number to stop):")
        if not inp.isdigit():
            break
        arr.append(int(inp))
find = int(raw_input("Enter the number you want to find: "))
print "Position of " + str(find) + " is " + str(linear_search(arr, find))


  # Part of Cosmos by OpenGenus Foundation
items = [5, 10, 34, 18, 6, 7, 45, 67]
target = 7

#Returns a boolean that indicates whether the target item is contained within
#the given list.
def linear_search(list, target)
  #Iterate over each item in the list
  list.each do |item|
    return true if item == target
  end

  false
end

found = linear_search(items, target)

if found
  puts "Found '#{target}'!"
else
  puts "'#{target}' was not found."
end


  fn search(vec: &[i32], n: i32) -> i32 {
        for i in 0..vec.len() {
            if vec[i] == n {
                return i as i32; // Element found return index
            }
        }
        return -1; // If element not found return -1
    }
fn main() {
    let arr = vec![1, 3, 45, 56, 8, 21, 7, 69, 12];
    let num = 56;
    let index =  search(&arr, num);
    if index != -1 {
        println!("Found {}, at index {}", num, index);
    }else {
        println!("{} not found!", num)
    }
}


      /* Part of Cosmos by OpenGenus Foundation */
object LinearSearch extends App {

  def linearSearch[A: Equiv](list: List[A], element: A): Option[Int] = {
    list match {
      case Nil => None
      case head :: tail => if (head == element) Some(0) else (linearSearch(tail, element).map(_ + 1))
    }
  }

  val list = (0 to 1000) map (_ => scala.util.Random.nextInt(1000))
  val element = scala.util.Random.nextInt(1000)
  val output = linearSearch(list.toList, element)
  Console.println(s"Index: $output")

}


    //
    //  linear_search.swift
    //  test 
    //  Created by Kajornsak Peerapathananont on 10/14/2017 BE.
    //  Copyright © 2560 Kajornsak Peerapathananont. All rights reserved.
    //  Part of Cosmos by OpenGenus Foundation
import Foundation

/*
 Input : array of item and the element that want to be search
 Output : index of element (if found) or else -1
 */
func linear_search<T : Equatable>(array : [T], element : T) -> Int{
    for (index, item) in array.enumerated() {
        if(item == element){
            return index
        }
    }
    return -1
}


Optimizations

The simple Linear search algorithm can be modified in small respects to get an optimized results:

Optimization 1: Linear search with a sentinel

The basic algorithm above makes two comparisons per iteration

By adding an extra record w to the list (a sentinel value) that equals the target, the second comparison can be eliminated until the end of the search, making the algorithm faster. The search will reach the sentinel if the target is not contained within the list.

In practice, this optimization makes n+1 comparisons in the worst case.

Steps:

  • Step 1: Set i to 0.
  • Step 2: If Li = T, go to step 4.
  • Step 3: Increase i by 1 and go to step 2.
  • Step 4: If i < n, the search terminates successfully; return i else, the search terminates unsuccessfully.

Optimization 2: Linear search in an ordered table

If the list is ordered such that L0 ≤ L1 ... ≤ Ln−1, the search can establish the absence of the target more quickly by concluding the search once Li exceeds the target. This variation requires a sentinel that is greater than the target.

Steps:

  • Step 1: Set i to 0.
  • Step 2: If Li ≥ T, go to step 4.
  • Step 3: Increase i by 1 and go to step 2.
  • Step 4: If Li = T, the search terminates successfully; return i else, the search terminates unsuccessfully.

Applications


Linked List is the preferred search algorithm in the following cases:
  • List contains few elements (exact number depends on usage factors).
  • List is unordered.
  • If the content of the list change frequently, repeated re-organization can be an overload. In such a case, linear search is the preferred search algorithm.

Conclusion

In theory other search algorithms may be faster than linear search but in practice even on medium-sized arrays (around 120 items or less) it might be infeasible to use anything else. On larger arrays, it is adviced to use faster search methods as if the data is large enough, the initial time to prepare the data is comparable to many linear searches.