DSA- Linear Search

#java #algorithms

linear Search - is algorithm which starts searching from index 0 till the element finds.

This algorithm also worst-case algorithm. If element not available, it iterates through the elements till end.

Best Case - O(1)
Worst case - O(n) where n is the size of the array.

public class LinearSearch {
    public static void main(String[] args) {
        int[] arr = new int[5];
        for(int i=0;i<arr.length;i++) {
            arr[i]=i;
        }
        int target = 2;
        System.out.println("element found in the array at index " +linearSearch(arr, target));
        int targetNotInArray = 100; // to prove worst case
        System.out.println("This will iterate through the array and element "
                + "is not found in array and return false" +
        linearSearch(arr, targetNotInArray));
    }

    static int linearSearch(int[] arr, int target) {
        if (arr.length == 0) { // if the array has no element
            return -1;
        }
        // looping through the array to find element
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }

        return -1;
    }
}

Top comments (3)

Vincent A. Cicirello • Feb 14 '23

Two very minor errors in your post.

First, you indicate worst case is o(n). It is actually O(n). Casing matters. Your o(n) means strictly lower order than n (i.e., it excludes same order as n). While O(n) means at most order n. Little o and Big O relate to each other in a similar way as < and <= relate to each other.

Second, best case should be O(1) and not o(1) for the same reason.