Linear search

From Algorithmist
Jump to: navigation, 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[edit]

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[edit]

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