Linear search (sequential search) is the most simple approach to find out, whether the array (or a different data structure) contains some element. The principle of linear search is trivial – iterate over all elements stored in the structure and compare them with the searched one. In the worst case – the last element is equal to the searched one or the structure does not contain the element at all – linear search has to perform comparisons, hence the asymptotic complexity of the algorithm is .

Usage

We use linear search, when we have no information about the ordering of elements in the given structure and when the data structure itself does not support more efficient ways to find an element (for example hashing).

If the data structure supports random access and its elements are ordered, we should use more effective algorithms – binary search or interpolation search.

Code

    /**
     * Linear search
     * @param array array to be searched in
     * @param value value to be searched for
     * @return index of the searched value, -1 if it is not contained in array
     */
    public static int linearSearch(int[] array, int value){
        for(int i = 0; i < array.length; i++){
            if(array[i] == value) return i;
        }
        return -1;
    }