If each component is equally likely to be searched, then linear search has an average case of n+1/2 comparisons, but the average case can be affected if the search probabilities for each component vary. In computer science, a linear search or sequential search is a method for finding an component within a list.

A linear search sequentially checks each component of the list until it finds an component that matches the target value. If the algorithm reaches the end of the list, the search terminates unsuccessfully.

```
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Linear Search https://en.wikipedia.org/wiki/Linear_search
*
* Worst - O(n)
* Best - O(1)
* Average - O(n)
*/
def linearsearch[A](list: List[A], key: A): Option[A] = {
def search(as: List[A]): Option[A] =
if (as.isEmpty) None
else if (as.head == key) Some(as.head)
else search(as.tail)
search(list)
}
```