Linear Search is a brute force approach or sequential approach for finding value in a list of values. Even though, it is a single algorithm, can be written in many ways to simplify algorithmic time complexity based on input values. Linear Search can be a Brute force solution, it’s worst cost is proportional to the number of elements in the list. Linear search with sorted array as an input, we can improve the complexity by checking condition that the element is more than that it is being compared with, we can just ignore searching in the later part of the array. Some times Recursion is easy to code, Linear search can be written in a recursive fashion.
Here is the implementation for Linear Search Algorithm variations in Java
1.Linear Search (Bruteforce)
/**<p>Finding an element through linear search --BruteForce method</p>
* @param a
* @param number
* @return searchIndex
* Time Complexity :
* Best case : O(1)
* Worst case : O(n)
*/
public static int linearSearch(int[] a,int number){
//length of the array
int n=a.length;
//Bruteforce method :: loop through n numbers if element found return the index, else return -1
for(int i=0;i<n;i++){
if(a[i]==number){
return i;
}
}
return -1;
}2.Linear Search with Recursion
/**
* <p>Recursive solution for Linear Search</p>
* @param keys
* @param key
* @param low
* @param high
* @return
*/
public static int linearSearchWithRecursion( int[] keys, int key, int low, int high ) {
if (low > high) {
// There are no more keys left.
return -1;
} else if (keys[ low ] != key) {
// Search for key in remaining keys.
return linearSearchWithRecursion( keys, key, low + 1, high );
} else {
// We've located key.
return low;
}
}A sample Test client for above two algorithms
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={1,4,5,3,2,0,8,6};
int searchIndex=linearSearch(arr,0);
if(searchIndex==-1)
System.out.println("Element you are searching for is not found!");
else
System.out.println("Element at an Index position "+searchIndex);
int recursiveIndex=linearSearchWithRecursion(arr,0,0,arr.length-1);
if(recursiveIndex==-1)
System.out.println("Element you are searching for is not found!");
else
System.out.println("Element at an Index position "+recursiveIndex);
}3.Sorted Array Linear Search
package com.jminded.algorithms.search;
public class SortedArrayLinearSearch {
/**
* @author Umashankar
* {@link https://jminded.com}
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={0,1,2,4,5,6,7};
int searchIndex=linearSearch(arr,3);
System.out.println("Element at search index "+searchIndex);
searchIndex=linearSearch(arr, 7);
System.out.println("Element at search index "+searchIndex);
}
/**
* <p>UnSorted Array LinearSearch</p>
* @param a
* @param number
* @return
* Time Complexity :: O(n)
* Space Complexity :: O(1)
*/
public static int linearSearch(int[] a,int number){
int n=a.length;
for(int i=0;i<n;i++){
if(a[i]==number)
return i;
/*As it is sorted array, no need to search for element after
crossing the array number greater than the number we want to search.*/
else if(a[i]>number)
return -1;
}
return -1;
}
}