The Algorithm :

In computer science, a linear search or sequential search is a method for finding an element within an array. It sequentially checks each element of the array until a match is found or the whole array has been searched. It can work both when the elements in the array are stored or unsorted.

A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the array. If each element is equally likely to be searched, then linear search has an average case of (n+1)/2 comparisons, but the average case can be affected if the search probabilities for each element vary. Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short arrays.

Let us take an array {63, 17, 96, 38, 3, 43, 35, 82, 57, 90} as an example to find 35 using linear search.

As shown in the image, each element of the array is checked until the element is found. In this case the number 35 will be found at the 6th index.

The Code :

import java.util.*;
class linear
{
    public static void main()
    {
        Scanner sc = new Scanner(System.in);
        int num;
        int pos = 0;
        int found = 0;
        int x[] = {63,17,96,38,3,43,35,82,57,90};
        
        System.out.println("Enter the number to be searched : ");
        num = sc.nextInt();
        for(int i = 0; i < 10; i++)
        {
            if(x[i] == num)
                {
                    found = 1;
                    pos = i;
                    break;
                }
            
        }
       System.out.println("The array is : ");
       for(int i = 0; i < 10; i++)
        {
            
              System.out.print(x[i] + " ");
        }
       System.out.println();
        if(found ==1)
            System.out.println("The number " + num + " was found at index number " + pos );
       else
            System.out.println("Not found in the array :( ");
 }
}

The Linear Search Algorithm has :

A worst case performance of O(n)

A best case performance of  O(1)

An Average performance of O(n)

A worst case space complexity of O(1) iterative

The github link for the program is :

https://github.com/AdityaSareen06/java/blob/master/linear.java

The picture has been taken from :

Business vector created by rawpixel.com – www.freepik.com

If you want to read about the binary search algorithm :

Visits: 157

4 Replies to “Linear Search”

Leave a Reply

Your email address will not be published. Required fields are marked *