Linear search

Linear search is a searching algorithm. It sequentially checks every element in an array until it finds the required value or all the elements of the array is checked. Worst case complexity is $O(n)$ and best case is $O(1)$ .

Pseudo-code

A is an array of size n and k is the value we want to find.

linearSearch (A, n, k)
1. for i from 1 to N
2.     if A[i] = k
3.         return i
4. return NOT-FOUND

Recursive:

linearSearch (A, n, k, i)
1. if i > n
2.     return NOT-FOUND
3. if A[i] = k
4.     return i
5. return linearSearch (A, n, k, i+1)

Optimizations

A small improvement can be made. At line 1 we are checking $n+1$ times if we have gone past the last index of the array A? At line 2 we are checking $n$ times if index i has the value we are searching for.

linearSearch (A, n, k)
1. Store the value of A[n] in variable last
2. Replace the value of A[n] with k
3. Set i = 1
4. while (A[i] != k)
5.     i++;
6. Restore the value of A[i] from variable last
7. if(i < n OR a[n] = k)
8.     return i
9. return NOT-FOUND