Linear Search using Java with Code Example

Explanation of Linear Search

Linear search is a simple search algorithm that iterates over a list of elements and compares each element with the target element until a match is found or the end of the list is reached.

To understand linear search, consider the following list of numbers: [5, 3, 8, 4, 2]. Suppose we want to find the position of the element 8 in the list. The linear search algorithm starts at the beginning of the list and compares each element with the target element until a match is found.

The figure below shows the linear search algorithm for finding the element 8 in the list [5, 3, 8, 4, 2]:

Index 0: 5 -> 8 not found yet

Index 1: 3 -> 8 not found yet

Index 2: 8 -> 8 found at index 2

As we can see from the figure, the linear search algorithm compares each element in the list with the target element until it finds a match at index 2, where the element 8 is located.

If the target element is not present in the list, the linear search algorithm will iterate over all the elements in the list and return a “not found” result. The figure below shows the linear search algorithm for finding the element 7 in the list [5, 3, 8, 4, 2]:

Index 0: 5 -> 7 not found yet

Index 1: 3 -> 7 not found yet

Index 2: 8 -> 7 not found yet

Index 3: 4 -> 7 not found yet

Index 4: 2 -> 7 not found yet

Not found

Another example:

The following figure illustrates the process of linear search for finding the number 7 in the list [5, 9, 3, 7, 1, 8]:

[5, 9, 3, 7, 1, 8]
 ^                    (compare 5 with 7, no match)
    ^                 (compare 9 with 7, no match)
       ^              (compare 3 with 7, no match)
          ^           (compare 7 with 7, match found)

As can be seen from the figure, linear search requires iterating through each element in the list, which can be time-consuming for very large lists. However, for small lists or lists that are not sorted, linear search can be a good option.

In summary, linear search is a simple search algorithm that iterates over a list of elements and compares each element with the target element until a match is found or the end of the list is reached. Linear search is easy to implement, but it can be slow for large lists as it has a time complexity of O(n), where n is the number of elements in the list.

Java Code Example on Linear Search

Here is an example of a linear search implementation in Java:

public class LinearSearch {
    public static int search(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Target found at index i
            }
        }
        return -1; // Target not found
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        int target = 8;
        int index = search(arr, target);
        if (index != -1) {
            System.out.println("Target found at index " + index);
        } else {
            System.out.println("Target not found");
        }
    }
}

In this implementation, the search method takes an array of integers arr and a target integer target, and returns the index of the target in the array if found, or -1 if not found. The search method iterates over each element in the array using a for loop, and checks if the current element is equal to the target. If the target is found, the method returns the index of the current element, which is the index of the target in the array. If the loop finishes without finding the target, the method returns -1 to indicate that the target was not found.

In the main method, we create an example array arr and set the target integer to 8. We then call the search method with arr and target, and store the result in the index variable. We then check if the index is -1 or not, and print the appropriate message to the console.

Note that linear search has a time complexity of O(n), where n is the number of elements in the array, so it is not the most efficient algorithm for large arrays. However, it is a simple algorithm to understand and implement.

Also, see the example code JavaExamples_NoteArena in our GitHub repository. See complete examples in our GitHub repositories.

Follow us on social media
Follow Author