Linear Search in Java

Introduction to Linear search in Java

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 the target element in the array arr. If the element is not found in the list it must terminate and must return a valid result.

Example

Let us say we are given a list containing all the students' results. You're supposed to find your name in the first column to find the result.

The very obvious way to do so is to read each name from the list until you find your name. This is nothing but a linear search algorithm.

Algorithm

The Linear Search program in Java is a search algorithm used to find the index of the target element from the array. It sequentially visits each element in an array to find the index of the specified element.

Though it is not the fastest algorithm it has various applications and advantages. It is suitable for smaller lists, lists with unsorted data, etc.

Other algorithms like Binary Search and Hash Tables are more efficient and faster searching algorithms; thus, linear search is rarely used, but they require certain conditions to be satisfied by the container or some pre-computations. On the other hand, linear search is simple to implement with no prerequisites.

How Linear Search Works?

A linear search algorithm traverses the entire array from start to end using a loop. If the element at the current index is equal to the target element, then it returns the index; otherwise, it goes to the next element of the array. If the target element is not found in the array, it returns -1.

Let us now see the algorithm for the same:

• Initialize N by the array's length using arr.length.
• Using for loop in Java visit each element from index 0 to N-1.
• At each iteration, compare the current index element with the target element.
• If they are equal return index+1 as the position of the target element in the array, else visit the next element.
• If none of the elements match and we reach the end of the list, return -1 which indicates the element is not present in the list.

The worst-case time complexity of the linear search in Java is O(n). This occurs when the element is present at the $Nth$ index or absent. The space complexity for linear search programs in Java is O(1) as no extra space is being used.

Example Program

Now, let us look at the Java code for Linear Search. We will take user input for the array and the target element. In this case, the array is [50, 98, 73, 26, 11] and the target element is 26.

Output:

Explanation:

• In the example above, we use the Scanner class to take user input for the array and the target element and store the elements in an array.
• We create another method, Search(), that searches and returns the index of the target element. It uses for loop to visit each element of the array.
• At each iteration, the target element is compared with the element of the array at that index.
• If the target element is found then it returns the index else it continues with the next iteration. If the target element is not present in the array we return -1.

Recursive Approach

We can also implement a linear search algorithm with the help of recursion. The recursive approach for linear search in Java is as follows:

• We start searching from the last element i.e. from $(N-1)th$ index (as per zero indexing).
• If the value of N argument becomes zero, we return -1. This becomes our base condition, which implies that the element doesn't exist.
• Else we check the element at the $(N-1)th$ index. If it is equal to the target element, we return N. Else, we recursively call the Search() method for the N-1 size of the array.

Output:

Explanation:

• The linear search algorithm can also be implemented using recursive code. In this method, we start searching from the last element of the array.
• If N becomes 0, then the element is not present in the array; thus, we return -1. This becomes our base condition.
• Now, if N is not zero, we see if the element at the index N-1 equals the target element. If we find the element, we return it. Else, we look for the next element in the array.