Linear Search: Searching Algorithm

The aim of any search algorithm is to determine in a given value appears within a sequence of n values.

When the values are unsorted, the standard approach to solve this problem is to compare each element, with the given value until either find the element or you have examined all the elements.

Code:

class LinearSearch {
        static public void linearUnordSearch(int[] in, int key) {
                for(int i=0; i<in.length; i++) {
                        if(in[i] == key) {
                                System.out.println("Element: " + key + ", found at index: " + i);
                                return;
                        }
                }

                System.out.println("Element: " + key + " not found");
        }

        static public void linearOrdSearch(int[] in, int key) {
                for(int i=0; i<in.length; i++) {
                        if(in[i] > key)
                                break;

                        if(in[i] == key) {
                                System.out.println("Element: " + key + ", found at index: " + i);
                                return;
                        }
                }

                System.out.println("Element: " + key + " not found");
        }

        static public void main(String[] args) {
                int[] ar = {8, 2, 5, 1, 7, 4, 0};

//              linearUnordSearch(ar, 7);
//              linearUnordSearch(ar, 10);

                linearOrdSearch(new int[]{1, 3, 4, 6, 7, 9}, 5);
                linearOrdSearch(new int[]{1, 3, 4, 6, 7, 9}, 7);
        }

}

Efficiency:

1. Worst Case:
For Linear Search, the worst case happens when the element to be searched is not present in the input array at all.
When element is not present, comparison is done on all elements of the array.
Therefore, for n number of input elements in the array,
Worst case time Complexity = O(n)

2. Average Case:
Possible cases = (at position 1), (at position 2), ..., (at position n-1), (at position n), not present
So total number of possible cases = n+1

Therefore,

3. Best Case:
Here the best case occurs when the required element is present at the first location of the given input array.
The number of operations in the best case is constant, i.e., independent of number of input elements.
Therefore Best case time Complexity = O(1)