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-

1. Start with the first element in the array or list.
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.

Keep Learning.. Happy Learning.. 🙂

Recommended -