Searching is a very important problem in field of computer science.

Searching can be divided into three main categories :

1) Linear search

2) Binary search

3) Hashing.

This post will explain Linear search.

Linear search is simply iterating through all the elements of array , till you find the item in question.

Worst case complexity of this algorithm is O(N) while best case is O(1).

For example : Given a List of N elements find element x. If present, return its position.

Lets write a simple method to implement Linear search. See following method LinearSearch() this method takes two parameters, first is an array of integers and second is the element to search in that array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int LinearSearch(int[] a, int k) { // Travel the array from start to end for(int i=0;i<a.Length;i++) { // For every element of array check if current element of array is equal to k or not if(a[i] == k) { return i; // Element Found. } } return -1; } |

So above method returnsÂ -1 if element is not present in the array or returns its position in array, ifÂ present. Linear search is very simple to understand and implement.