13.6.1. Linear Search Algorithm

Linear Search checks each element of the list sequentially to find the target value.

Linear search is a straightforward searching algorithm where we go through each element in the list one by one until we find the desired element, known as the target value. If we find the target, we successfully return its position; if not, we indicate that the target is not in the list.

Imagine looking for a specific book in a library where the books are not organized alphabetically or by genre. You would need to examine each book one by one until you find the book you're looking for, just like how a linear search checks each element sequentially.

Steps:

1. Start from the first element of the list.
2. Compare each element with the target value.
3. Return the index if a match is found; otherwise, return -1.

The linear search algorithm follows a simple sequence of steps: First, it begins with the first element of the list. Then, it compares that element to the target we are trying to find. If the element matches the target, the algorithm returns the index (or position) of that element in the list. If there are no more elements to check and no match has been found, the algorithm returns -1, indicating that the target is not present in the list.

Think of a treasure hunt where you need to look at each clue one by one. You start with the first clue, check if it’s the one you need (the target), and if it isn’t, you move to the next clue, repeating this process until you either discover the treasure (the match) or run out of clues (return -1).

Example:

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; // Target found
            }
        }
        return -1; // Target not found
    }
    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int target = 30;
        int index = linearSearch(arr, target);
        System.out.println("Element found at index: " + index); // Output: Element found at index: 2
    }
}

In this Java example of linear search, we define a method called linearSearch that takes an integer array and a target value as inputs. The method iterates through the array using a for-loop. If it finds an element that matches the target, it returns that element's index. If the entire array is checked and no match is found, it returns -1. In the main method, we set up a sample array and a target, demonstrating the search and printing the found index.

Imagine a box of assorted toys. If you want to find a specific toy, you will take each toy out one by one until you find it. The code does exactly this with an array of integers, searching through until it finds the target number or exhausts all options.

Time Complexity: O(n)

The time complexity of the linear search algorithm is denoted as O(n), where n is the number of elements in the list. This means that in the worst case, the algorithm must check each element once. If the target is the last element or not in the list at all, every element will be checked before concluding.

If you were searching for a book in a library, and the library had 1000 books, in the worst-case scenario, you might have to check all 1000 books to find the target book. This represents a linear relationship between the number of books and the time taken to find one.

--