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
01./**02. * Linear search03. * @param array array to be searched in04. * @param value value to be searched for05. * @return index of the searched value, -1 if it is not contained in array06. */07.public static int linearSearch(int[] array, int value){08. for(int i = 0; i < array.length; i++){09. if(array[i] == value) return i;10. }11. return -1;12.}