Linear Search

 

Linear Search

Linear Search is defined as a sequential search algorithm that starts at one end and goes through each element of a list until the desired element is found, otherwise the search continues till the end of the data set. It is the easiest searching algorithm.

Linear Search Algorithm

Step 1: First, read the search element (Target element) in the array.

Step 2: In the second step compare the search element with the first element in the array.

Step 3: If both are matched, display “Target element is found” and terminate the Linear Search 

function.

Step 4: If both are not matched, compare the search element with the next element in the array.

Step 5: In this step, repeat steps 3 and 4 until the search (Target) element is compared with the 

last element of the array.

Step 6 – If the last element in the list does not match, the Linear Search Function will be 

terminated, and the message “Element is not found” will be displayed.

Follow the given steps to solve the problem:

1. Set the first element of the array as the current element.
2. If the current element is the target element, return its index.
3. If the current element is not the target element and if there are more elements in the array, set the current element to the next element and repeat step 2.
4. If the current element is not the target element and there are no more elements in the array, return -1 to indicate that the element was not found.

Example:

Given an array arr[] of N elements,

the task is to write a function to search a given element x in arr[].


Solution:

class LinearSearch { public static int search(int arr[], int x) { int N = arr.length; for (int i = 0; i < N; i++) { if (arr[i] == x) return i; } return -1; } // Driver's code public static void main(String args[]) { int arr[] = { 2, 3, 4, 10, 40 }; int x = 10; // Function call int result = search(arr, x); if (result == -1) System.out.print( "Element is not present in array"); else System.out.print("Element is present at index " + result); } } Output: Element is present at index 3 Time complexity: O(N) Auxiliary Space: O(1)




Linear search Recursive approach:




Follow the given steps to solve the problem:

• If the size of the array is zero then, return -1, representing that the element is not found. This can also be treated as the base condition of a recursion call.
• Otherwise, check if the element at the current index in the array is equal to the key or not i.e, arr[size – 1] == key
• If equal, then return the index of the found key

Below is the implementation of the above approach:

// Java Recursive Code For Linear Search

import java.io.*;

 

class Test {

    static int arr[] = { 5, 15, 6, 9, 4 };

 

    // Recursive Method to search key in the array

    static int linearsearch(int arr[], int size, int key)

    {

        if (size == 0) {

            return -1;

        }

        else if (arr[size - 1] == key) {

            // Return the index of found key.

            return size - 1;

        }

        else {

            return linearsearch(arr, size - 1, key);

        }

    }

 

    // Driver method

    public static void main(String[] args)

    {

        int key = 4;

 

        // Function call to find key

        int index = linearsearch(arr, arr.length, key);

        if (index != -1)

            System.out.println(

                "The element " + key + " is found at "

                + index + " index of the given array.");

 

        else

            System.out.println("The element " + key

                               + " is not found.");

    }

}

Output

The element 4 is found at 4 index of the given array.

Time Complexity: O(N)

Auxiliary Space: O(N)

Advantages of Linear Search:

• Linear search is simple to implement and easy to understand.
• Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of any data type.
• Does not require any additional memory.
• It is a well suited algorithm for small datasets.

Drawbacks of Linear Search:

• Linear search has a time complexity of O(n), which in turn makes it slow for large datasets.
• Not suitable for large array.
• Linear search can be less efficient than other algorithms, such as hash tables.

When to use Linear Search:

• When we are dealing with a small dataset.
• When you need to find an exact value.
• When you are searching a dataset stored in contiguous memory.
• When you want to implement a simple algorithm.