Linear search technique

What is linear or sequential search?
Linear or sequential search is a simple algorithm. It iterates through items until the item has been found, which makes it a linear algorithm. -
Complexity of the linear search is O(n), where n is the number of items to go through.

Algorithm of linear search:-
Steps:-
1. start from the leftmost item or element from the array and one by one compare with searching element with each element of array.
2. If searching element matches with an element, return the index.
3. If searching element does not match with any elements of array, return -1.

Example:-

C implementation of linear search:-

Output:-

Java implementation of linear search:-

Output:-

Complexity analysis:- To calculate complexity of linear search or any other kind of searching, we just calculate the number of comparisons.
In case of linear search, we have three possibilities-
1. Best case:- The best case will be when the element we are searching is present at first position in the array.
for example:-      array[0]==x
In this case only one comparison will be made irrespective of the array size. 
so complexity will be C(n)=O(1)

2. Worst case:- The worst case will be when the element we are searching is not present at all in the array or is present at last position.
for example:-     array[n-1]==x
In this case n comparisons will be done. 
so complexity will be C(n)=O(n)

3. Average case:- The average case will be when searching element can be found at any position in the array so number of comparisons any where 1 to n.
Thus, the probability of x being at any location will be one by n.

As n will increase the time required to find out n element will increase linearly.
so complexity will be C(n)=O(n)