THE education site for computer science and ICT
2. Linear (or Sequential) Search
This algorithm will find the location of a specified item within an array (or list). Its strength is that the list does not have to be in any order.
For a list of n items
The algorithm is:
1. Specify the item to be searched T
2. Set a list pointer to its beginning $i$ = 0
2. Compare T with the first element in the list ($L_0$) as the first element is position zero
3 If $T$ = $L_0$ then stop search and return 0
4. Else increment $i$
5. Compare to next element $L_i$
6. If $T$ = $L_i$ then stop search and return $i$
7. Repeat until the end of the list $L_{n-1}$ is reached and return a 'not found' signal
Linear search clearly has a best, worst and average outcome in time complexity. The fastest outcome is if the first element is the target hence only 1 step needed, the worst case is if the item was not in the list and it took $n$ steps to find that out, if the list is in a random order then the average outcome will be half the list length
| Algorithm | Best case | Worst case | Average case | Space complexity |
|---|---|---|---|---|
| Linear search | 1 | $O( n)$ | $O( \frac {(N+1)} 2)$ | $O(1)$ |
As this is a simple algorithm to code and the list does not have to be in any order, this is a good one to use as long as the average case time due to list length is acceptable.
Challenge see if you can find out one extra fact on this topic that we haven't already told you
Click on this link: Coding for linear search