# Linear Search Algorithm and its Implementation

Linear search algorithm is one of the most basic algorithm in computer science to find a particular element in a list of elements.
So before starting this tutorial on Linear Search Algorithms let’s first see what we mean by a Searching problem

```Given a set of data -> e.g., int [] arr = {10, 2, 7, 9, 7, 4};
and a particular value -> e.g., int val = 7;
Find the first index of the value in the data.
e.g., return index = 2 (because arrays follow 0 index structure i.e. the index of first element is 0 and so on)
```

In this algorithm we compare the required element with each element in the list or array until it is find or until we reach the end of the list.

```Pseudocode:-
# Input: Array D, integer key
# Output: first index of key in D, or -1 if not found

For i = 0 to last index of D:
if D[i] equals key:
return i
return -1

```

#### Asymptotic Analysis

Since this algorithm compares every element to find the required one its complexity in all the cases remains order of n i.e. O(n) (where n is number of elements in the list) and its expected cost is also proportional to n provided that searching and comparing cost of all the elements is same.

Worst case time complexity – O(n)
Average case time complexity – O(n)

#### So the idea is-

2. Compare it with the given key, if key and value at current index are same, return the current index.
3. Else increase the index value and repeat step 2 until end of list is reached.

#### RECURSIVE Implementation of Linear search in C programming language

```#include <stdio.h>

//A linear search algorithm to find and return index of the searched element
int recursiveLinearSearch(int array[], int arraySize, int value, int index)
{
if(index<arraySize){
if(array[index] == value)
return index;
else
return recursiveLinearSearch(array, arraySize, value, index+1);
}
else{
return -1;
}
}

int main(void)
{
int array[] = {10, 2, 7, 5, 15, 30, 8, 6}; // input array
int value = 30;	//value to be searched
int arraySize = sizeof(array)/sizeof(array[0]);
int result = recursiveLinearSearch(array, arraySize, value, 0); //calling function to apply linear search
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
```
```Output:-
Element is present at index 5```

#### ITERATIVE Implementation of Linear search in C programming language

```#include <stdio.h>

//A iterative linear search algorithm to find and return index of the searched element
int iterativeLinearSearch(int array[], int arraySize, int value)
{
int i=0;

for(i=0; i < arraySize; i++){
if(value == array[i]){
return i;
}
}
return -1;
}

int main(void)
{
int array[] = {10, 2, 7, 5, 15, 30, 8, 6}; // input array
int value = 30;	//value to be searched
int arraySize = sizeof(array)/sizeof(array[0]);
int result = iterativeLinearSearch(array, arraySize, value); //calling function to apply linear search
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
```
```Output:-
Element is present at index 5```

#### Implementation of Linear Search in Java

```package com.codingeek.algorithms.search;

public class LinearSearchImplementation {

public static void main(String[] args) {
Integer[] inputArray = { 10, 2, 7, 5, 15, 30, 8, 6 };
Integer key = 30;
int result = new LinearSearch().linearSearch(inputArray, key);

if (result == -1)
System.out.println("No such element exists in input");
else
System.out.println("Element exixts at " + result + " index");
}
}

class LinearSearch {
private static final Integer FAILURE = -1;

public int linearSearch(Integer[] inputArray, Integer key) {
for (int i = 0; i < inputArray.length; i++) {
if (inputArray[i].equals(key)) {
return i;
}
}
return FAILURE;
}
}

```
```Output:-
Element is present at index 5
```

Do share the wisdom and motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

### Recommended -

Subscribe
Notify of
Inline Feedbacks
8 years ago

On the Java part, you made a huge mistake, if you are working with Integer you should do a comparison using equals, this is necessary because you are comparing objects and not primitives values, so or you use equals or you change from Integer to int.

hiteshgarg21
8 years ago

Yeah thanks @Francisco, How can I miss such a point, but this happens because I tested it only on smaller values i.e. between -128 to 127 including end points and it runs correctly (http://ideone.com/RYX53Q).. Thanks for pointing it out.. Corrections are done..
Source of information – http://stackoverflow.com/questions/5581913/integer-wrapper-class-and-operator-where-is-behavior-specified

2
0