Linear Search

Linear search, often referred to as sequential search, is a straightforward searching algorithm.

Its essence is to traverse an array or list, element by element, to locate the desired value.

How does it work?

1. Start from the first element.
2. Compare the current element with the desired value.
3. If they match, return the current position.
4. If they don’t match, move to the next element.
5. Repeat steps 2-4 until you find a match or reach the end of the array.

Time Complexity

For an array of n elements:

• Best Case: O(1) – when the desired value is at the first position.
• Worst Case: O(n) – when the desired value is at the last position or not present at all.

Java Code

public class LinearSearch {
    
    public static int search(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x) {
                return i;  // Element found, return its index
            }
        }
        return -1;  // Element not found
    }

    public static void main(String[] args) {
        int[] sampleArray = {10, 25, 31, 47, 52, 68};
        int desiredValue = 47;

        int result = search(sampleArray, desiredValue);
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Summary

Linear search is simple and doesn’t require any preliminary setup like sorting.

However, for larger lists or arrays, it can be inefficient compared to other searching algorithms like binary search.

It’s best suited for smaller lists or when the list’s structure is unknown.