Exploring Linear Search

In the world of programming, searching for a specific element in an array is a common task. Linear search is a simple search algorithm that is widely used when the array is not sorted or when the program does not have any prior knowledge about the arrangement of elements in the array.

As a senior engineer with a strong background in Java and Spring Boot, you are likely familiar with the concept of searching algorithms. Think of a linear search as similar to finding a particular item in an unorganized room. You would start from the first item and continue until you find the desired item.

Let's look at an example to understand the linear search algorithm:

1public class LinearSearch {
2
3    public static int linearSearch(int[] arr, int target) {
4        for (int i = 0; i < arr.length; i++) {
5            if (arr[i] == target) {
6                return i;
7            }
8        }
9        return -1;
10    }
11
12    public static void main(String[] args) {
13        int[] arr = {5, 10, 15, 20, 25};
14        int target = 15;
15        int index = linearSearch(arr, target);
16        if (index != -1) {
17            System.out.println("Element found at index: " + index);
18        } else {
19            System.out.println("Element not found");
20        }
21    }
22
23}

In this example, we have an array arr with elements [5, 10, 15, 20, 25]. We want to find the index of the target element which is 15. The linearSearch method iterates through the array from the beginning and compares each element with the target value. If a match is found, the method returns the index of the element; otherwise, it returns -1.

In the main method, we call the linearSearch method and store the returned index in the index variable. If the index is not -1, we print the message 'Element found at index: x' where x represents the index value. Otherwise, we print 'Element not found'.

The linear search algorithm has a time complexity of O(n), where n is the number of elements in the array. This means that in the worst case scenario, the algorithm will iterate through all the elements in the array. The space complexity of the linear search algorithm is O(1) as it only requires a constant amount of additional space to store the target and index variables.

While linear search is a simple and straightforward algorithm, it is not the most efficient option for large arrays or when searching needs to be performed frequently. In such cases, other searching algorithms like binary search or hash-based searching methods are preferred.

Now that you have learned about the linear search algorithm, take some time to experiment with different arrays and target values. See how the algorithm performs and think about possible optimizations or alternative approaches.

xxxxxxxxxx

public class LinearSearch {

​

    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 = {5, 10, 15, 20, 25};

        int target = 15;

        int index = linearSearch(arr, target);

        if (index != -1) {

            System.out.println("Element found at index: " + index);

        } else {

            System.out.println("Element not found");

        }

    }

​

}