# 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 ${\displaystyle O(n)}$ and best case is ${\displaystyle 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 ${\displaystyle n+1}$ times if we have gone past the last index of the array A? At line 2 we are checking ${\displaystyle 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
```