Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 15 minutes | Coding time: 6 minutes

Linear search (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.

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

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

### Example

Consider the following sorted list in which we want to find 6:

`-1 3 3 6 11 12 16 17 18 19`

We chose to compare with the first element -1 with 6. As -1 != 6, we move on.

The potential numbers are:

`3 3 6 11 12 16 17 18 19`

We compare 6 with the second element 3. As 3 != 6, we remove 3.

The potential numbers are:

`3 6 11 12 16 17 18 19`

We compare our target 6 with the first (3rd) element 3. As 3 != 6, we move on.

The potential numbers are:

`6 11 12 16 17 18 19`

We compare our target 6 with the first (3rd) element 3. As 6 == 6, we found our target and terminate the search 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

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