Linear Search

There are two search algorithms available for finding a target element within a list. One is linear search or sequential search and the other type is binary search. Linear search is very simple to implement and can be used in the application when the list has only a few elements or while you perform a single search in an unordered list. Linear search sequentially checks each element in the array until it finds an element that matches the target element.

If you need to search many values in the list, then it’s better to sort the list and use a faster method for example, binary search or build an efficient search data structure.

Algorithm

• Start from the left most element of the array and compare the element to be searched with each element in the array one by one.
• If the element being searched matches with an element in the array, then stop the search and come out of loop.
• If the element being searched does not match with any element in the array, then print element does not exist in the array.

Example

package com.sneppets.dsalgo;

import java.util.Scanner;

public class LinearSearchExample {
	
	public static void main (String args[]){
		
		int count, numOfElements, element, array[];
		
		//user input - source an input stream to be scanned
		Scanner input = new Scanner(System.in);
		
		System.out.println("Enter number of elements");
		
		//nextInt() scans the next token of the input as an 'int'
		numOfElements = input.nextInt();
		
		//create array to store all the elements
		array = new int[numOfElements];
		
		System.out.println("Enter " + numOfElements + " Elements" );
		
		//Store each element in the array
		for (count=0; count < numOfElements; count++){
			array[count] = input.nextInt();
		}
		
		System.out.println("Enter the element to be searched");
		element = input.nextInt();
		
		for (count=0; count < numOfElements; count++){
			
			if(array[count] == element){
				
				System.out.println("Element " + element + " is present at " + (count+1));
				//Element is found, stop the search and come out of for loop
				break;
			}
		}
		if (count == numOfElements){
			System.out.println(element + " does not exist in the array");
		}		
	}

}

Output

Enter number of elements
6
Enter 6 Elements
5
10
3
12
6
9
Enter the element to be searched
3
Element 3 is present at 3

Enter number of elements
6
Enter 6 Elements
33
6
3
20
7
8
Enter the element to be searched
21
21 does not exist in the array

Time Complexity Analysis

Best Case:

For list of n elements, the linear search has the best case, when the element being searched is the first element of the array. In this case only one comparison is needed.

Best Case Performance – O(1)

Average Case:

If each element in the array needs to be searched equally likely, then the linear search has an average case of n/2 comparisons.

Average Case Performance – O(n)

Worst Case:

If the element being searched in the array does not exist or occurs only once at the end of the list, then we need to do n comparisons.

Worst Case Performance – O(n)

So the time complexity of above algorithm is O(n), since in the worst case we need to iterate from first element to the last element i.e., n elements.

Space complexity

The space complexity of the above algorithm is O(1), since we don’t need any extra space to store anything. We just need to compare the given element with each element in the array one by one.

Conclusion

So the performance of linear search improves if the element being searched is in the beginning of the list than at the end. The point taken here is if some elements are much more likely searched than the other elements, then it is better to place them at the beginning of this list.

Linear search is rarely used because other search algorithms like binary search and hash tables, allow significantly faster searching compared to linear search.