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

- Start with the first element in the array or list.
- Compare it with the given key, if key and value at current index are same, return the current index.
- 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.**

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.

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