Linear Search

Linear search, also known as sequential search is used to find a specific value withing an array or a list. It checks each element one by one until desired element is found and end of the list is reached.

How it works ?

1. Start from first element in the array.

2. Compare the number to be found with each element in array by using for loop from index 0 to array length - 1.

3. If element is found return index.

4. If element is not found return -1.

Code

import java.util.Arrays;
class LinearSearch {
    public static void main(String[] args) {
        int[] array = {20, 40, 48, 50, 45};
        linearSearch(array, 48);
    }

    static int linearSearch(int[] array, int numberToFind) {
        for (int i = 0; i < array.length; i++) {
            if(array[i] == numberToFind) {
                System.out.println("Number found at index : " + i);
                return i;
            }
        }
        System.out.println("Number not found");
        return -1;
    }
}

Output

java -cp /tmp/mlKZBqbmts/LinearSearch
Number found at index : 2

=== Code Execution Successful ===

Characteristics:

1. Time Complexity : O(n) where n is the number of elements in array. In worst case, every element will be checked.

2. Space complexity : O(1) as it uses constant amount of additional space.

3. Linear search is most useful for small and unsorted arrays or lists.