Recursive

Linear search

Pinterest LinkedIn Tumblr

Linear search is a method to find a particular item in an array. It start to check each item and compare with search item until it finds. The linear search performs non-sorted items in the array.

Linear search is a simple search algorithm to find the items from the unsorted array. If you want to search the item in the sorted array, we can use Binary search. It searches an item in less number of comparison.

Write a program to implement linear search.

source Code

package com.dsacode.Algorithm.search;
 
import java.util.Arrays;
 
public class LinearSearch {
 
    public static int search(int a[], int x){
        for(int i = 0; i < a.length; i++){
            if(a[i] ==x)
                return i+1;
        }
        return -1;
    }
    public static void main(String[] args) {
         int[] array = {12, 55, 45, 11, 23, 20, 17, 24, 9};
         System.out.println("List of items in the array: "+ Arrays.toString(array));
         int pos = -1;
         System.out.println("Search '12' in the array using linear search");
         if( (pos= search(array,12)) == -1)
             System.out.println("Not found!");
         else
             System.out.println("Found in " + pos + " Position!");
    }
} 

Output

List of items in the array: [12, 55, 45, 11, 23, 20, 17, 24, 9]
Search '12' in the array using linear search
Found in 1 Position!

Algorithm Explanation

Linear search takes each item and compare all the items from the list sequentially.
If the search finds, it returns the item or position. Otherwise, it return -1.

Time Complexity

Best CaseAverage CaseWorst Case
O(1)O(n/2)O(n)

Reference

  1. http://en.wikipedia.org/wiki/Linear_search
  2. http://www.cs.toronto.edu/~andria/csc/108s01/lecture/slides/lec12_complexity.html

Write A Comment