DEV Community

Saravanan B
Saravanan B

Posted on

DSA- Linear Search

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;
    }
}

Enter fullscreen mode Exit fullscreen mode

Image description

Top comments (3)

Collapse
 
cicirello profile image
Vincent A. Cicirello

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.

Collapse
 
saravananb15 profile image
Saravanan B

Made the corrections. Thanks for letting me know the errors. I am a learner learning as well as making post here it helps me a lot.

Collapse
 
cicirello profile image
Vincent A. Cicirello

You're welcome