Java Linear Search Algorithm

Linear search is one of the most basic algorithms in computer science. It is used to find the position of a specific value in an array of data. Below let’s explore the linear search algorithm and how it works, as well as implement it using the Java programming language.

What is Linear Search?

Linear search, also known as sequential search, is a simple algorithm that searches for a specific value in an array of values by checking each element of the array one by one until the target value is found. The algorithm starts at the beginning of the array and compares each element with the target value until either the target value is found or the end of the array is reached.

How does Linear Search work?

Here is the basic pseudocode for the linear search algorithm:

for each item in the array
    if item == target value
        return the index of the item
return -1

As you can see, the algorithm loops through each element in the array and compares it with the target value. If the target value is found, the index of the element is returned. If the target value is not found after checking every element, the algorithm returns -1.

Implementing Linear Search in Java

Now that we understand how the linear search algorithm works, let’s implement it in Java. Here is the Java code for the linear search algorithm:

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

In this Java code, the linearSearch method takes an array of integers arr and a target value target. It loops through each element of the array using a for loop and compares each element with the target value. If the target value is found, the index of the element is returned. If the target value is not found after checking every element, the method returns -1.

Implementing Linear Search in Java using a while loop

We can also implement the linear search algorithm using a while loop. Here is the Java code for the linear search algorithm using a while loop:

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

In this Java code, the linearSearchWhile method takes an array of integers arr and a target value target. It uses a while loop to loop through each element of the array and compares each element with the target value. If the target value is found, the index of the element is returned. If the target value is not found after checking every element, the method returns -1.

The while loop implementation is similar to the for loop implementation, except that we manually increment the index i instead of using the for loop syntax.

By using a while loop instead of a for loop, we have more control over the loop conditions and can use the loop to perform more complex operations if necessary.

Time Complexity and Big-O for Linear Search

The time complexity of the linear search algorithm is $O(n)$, where $n$ is the number of elements in the array. This is because in the worst case scenario, the algorithm may need to check every element in the array before finding the target value. Therefore, the time it takes to complete the search grows linearly with the size of the array.

In terms of big-O notation, the linear search algorithm has a worst-case time complexity of $O(n)$ and a best-case time complexity of $O(1)$. The best-case scenario occurs when the target value is found at the beginning of the array, in which case the algorithm only needs to check one element before returning the index.

It is important to keep in mind the time complexity of an algorithm when working with large datasets, as a linear search algorithm may become computationally expensive with very large arrays.