Linear Search in Java: Simple Search Algorithm

In this article, we will explore the concept of linear search in Java, its implementation with sample code and output, the logical steps involved, its time and space complexity, applications, and conclude with its significance in various scenarios.

Table of Contents

What is Linear Search?

Linear Search is an uncomplicated search algorithm that iterates through each element of the array sequentially until it finds the target element or reaches the end of the list.

Java Implementations

We will implement Linear Search in Java using two different ways:

Linear Search in Java using Loop
Linear Search in Java using Recursion

Linear Search in Java: Using Loop

Java Code

public class LinearSearchExample {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 25, 30, 12, 8, 5, 16};
        int target = 12;
        int result = linearSearch(arr, target);
        if (result == -1) {
            System.out.println("Element not found in the array.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Output

Element found at index: 3

Logical Steps:

Start from the first element of the array.
Compare the current element with the target element.
If the current element matches the target element, return the index.
If the end of the array is reached without finding the target element, return -1 to indicate that the element is not present.

Linear Search using Recursion

Recursive implementation involves calling the search function recursively on a smaller subarray until the target element is found or the array is exhausted. Here’s an example:

public class RecursiveLinearSearch {
    public static int linearSearchRecursive(int[] arr, int target, int index) {
        if (index >= arr.length) {
            return -1; // Element not found
        } else if (arr[index] == target) {
            return index; // Element found
        } else {
            return linearSearchRecursive(arr, target, index + 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 25, 30, 12, 8, 5, 16};
        int target = 12;
        int result = linearSearchRecursive(arr, target, 0);
        if (result == -1) {
            System.out.println("Element not found in the array.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Output

Element found at index: 3

Time Complexity of Linear Search

The time complexity of linear search is O(n), where n is the number of elements in the array. In the worst-case scenario, when the target element is at the last position or not present in the array, the algorithm will iterate through all the elements. Therefore, the time taken to perform the search increases linearly with the size of the input.

Space Complexity of Linear Search

The space complexity of linear search is O(1) since it only requires a constant amount of extra space for storing variables like indices and the target element.

Applications of Linear Search:

Searching in small arrays: Linear search is suitable for searching in small arrays where the overhead of more complex algorithms is not justified.
Unsorted lists: Linear search can be used to find an element in an unsorted list, as it does not rely on any specific ordering of the elements.
Determining element presence: Linear search is useful for checking the presence of an element in an array or list.

Conclusion: Linear Search in Java

Linear search is a simple yet effective searching algorithm for finding an element in an array or list. It sequentially compares each element until the target element is found or the end of the list is reached. While it may not be the most efficient algorithm for large datasets, it serves as a fundamental concept in programming and lays the foundation for more complex search algorithms. Understanding the logical steps, time complexity, and space complexity of linear search in Java allows developers to make informed decisions when selecting the appropriate searching algorithm for their specific needs.