1. Introduction

Linear Search, also known as Sequential Search, is a straightforward approach to find a specific value within a list. It scans each element of the list sequentially until the desired value is found or the list ends.

2. Program Steps

1. Start from the leftmost element of the array.

2. Compare the element with the target value.

3. If they are equal, return the current index.

4. If they are not equal, move to the next element.

5. Repeat steps 2-4 until the end of the list or the target is found.

6. If the list ends and the target is not found, return -1.

3. Code Program

public class LinearSearch {

    // Function to implement linear search
    static int search(int arr[], int x) {
        for (int i = 0; i < arr.length; i++) {
            // If the element is found, return its index
            if (arr[i] == x)
                return i;
        }
        // Return -1 if the element is not found
        return -1;
    }

    // Driver method
    public static void main(String args[]) {
        int arr[] = {10, 20, 80, 30, 60, 50};
        int x = 50;
        int result = search(arr, x);
        if (result == -1)
            System.out.println("Element is not present in the array");
        else
            System.out.println("Element is present at index: " + result);
    }
}

Output:

Element is present at index: 5

4. Step By Step Explanation

1. LinearSearch: This is the main class that contains methods to perform a linear search on an array.

2. search(int arr[], int x): This method implements the linear search algorithm. It takes an array arr and a target value x to search for.

3. Inside the search method, we iterate over each element of the array using a for loop.

4. For each element, it's checked whether it matches the target value x.

5. If a match is found, the index of the matching element is returned.

6. If no match is found after checking all elements, -1 is returned to indicate that the element isn't in the array.

7. In the main method, an array and a target value are defined, and the search method is invoked. The result, which is the position of the target in the array or -1 if the target isn't found, is then printed.

Since Linear Search examines each item in the list, its worst-case time complexity is O(n), where n is the number of elements in the list.