Master Linear Search Algorithm – Theory to Implementation

Introduction to Searching:

The act of locating a particular element within a list is commonly referred to as searching. When the desired element is discovered within the list, the search operation is deemed successful, and the position of the element is returned. Conversely, if the search fails to locate the element, it is considered unsuccessful.

Among the widely recognized search methods are binary search and linear search. In this tutorial, we will delve into the implementation of a linear search program in Java.

About Linear Search Algorithm:

Linear search, also known as sequential search, is a simple searching algorithm that checks each element in a list sequentially until the target element is found or the end of the list is reached.

Here’s how the linear search algorithm works:

• Start from the beginning of the list/array.
• Compare the target element with each element of the list sequentially.
• If the target element matches an element in the list, return the index of the element.
• If the target element is not found after checking all elements, return -1 (indicating the element is not present in the list).

Problem Statement

We are given an array arr of size N and a target element say target. Now, our task is to find the index or position of target element in the array arr. If the element is not found in the list it must terminate and must return a valid result.

Here’s a simple pseudocode representation of linear search:

LinearSearch(arr, target):
    for each element in arr:
        if element equals target:
            return index of element
    return -1  // target not found

Linear search is straightforward and easy to implement. However, its time complexity is O(n), where n is the number of elements in the list/array. This means that the time taken to search increases linearly with the number of elements in the list. As a result, linear search is not the most efficient algorithm for searching large lists, especially compared to more efficient algorithms like binary search or hash tables.

Despite its simplicity, linear search can be useful in situations where:

• The list is short.
• The list is unordered.
• The overhead of sorting the list for a more efficient search algorithm (like binary search) outweighs the benefits.

Here’s a java code of linear search:

// Iterative Implementation of Linear Search in Java
class LinearSearch {
  public static int linearSearch(int array[], int x) {
    int n = array.length;

    // Going through array sequencially
    for (int i = 0; i < n; i++) {
      if (array[i] == x)
        return i; // Return the index where the element is found
    }
    return -1; // Return -1 if the element is not found in the array
  }

  public static void main(String args[]) {
    int array[] = { 2, 4, 0, 1, 9 };
    int x = 1;

    int result = linearSearch(array, x);

    if (result == -1)
      System.out.print("Target Element not found");
    else
      System.out.print("Target Element found at index: " + result);
  }
}

Recursive Approach:

In this recursive version of linear search, the method linearSearchRecursive takes four parameters: the array arr[], the left index l, the right index r, and the target element x. It searches for x recursively within the subarray defined by arr[l..r].

The base cases for the recursion are:

• If r < l, which means the search space is empty, return -1.
• If the element at index l is equal to x, return l.
• If the element at index r is equal to x, return r.

If none of the base cases are met, the method recursively calls itself with the subarray arr[l+1..r-1].

public class RecursiveLinearSearch {
    // Recursive function to search x in arr[l..r]
    public static int linearSearchRecursive(int arr[], int l, int r, int x) {
        if (r < l)
            return -1;
        if (arr[l] == x)
            return l;
        if (arr[r] == x)
            return r;
        return linearSearchRecursive(arr, l + 1, r - 1, x);
    }

    public static void main(String args[]) {
        int arr[] = { 2, 4, 0, 1, 9 };
        int x = 1;

        int result = linearSearchRecursive(arr, 0, arr.length - 1, x);

        if (result == -1)
            System.out.println("Target Element not found");
        else
            System.out.println("Target Element found at index: " + result);
    }
}

Complexity of Linear Search:

• Time-Complexity: O(n)
• Space-Complexity: O(1)

In summary, linear search is a basic but effective algorithm for searching elements in a list sequentially. However, its efficiency decreases with larger lists, making it less practical for large-scale applications where faster search algorithms are needed.

Deependra Singh

Hello, my name is Deependra Singh. I hold B.tech degree in Computer Science & Engineering from Institute of Engineering & Technology, Lucknow. Currently, I am working in Steel Authority of India Limited as a Software Developer.