Randomized Sequential Search

We can improve the worst case of sequential search in a probabilistic sense, if the element belongs to the set (successful search) and we have all the elements in advance (off-line case). Consider the following randomized algorithm. We flip a coin. If it is a head, we search the set from $1$ to $n$, otherwise, from $n$ to $1$. The worst case for each possibility is $n$ comparisons. However, we have two algorithms and not only one. Suppose that the element we are looking for is in position $i$ and that the coin is fair (that is, the probability of head or tail is the same). So, the number of comparisons to find the element is $i$, if it is a head, or $n - i + 1$ if it is a tail. So, averaging over both algorithms (note that we are not averaging over all possible inputs), the expected worst case is

$$\frac{1}{2} \times i + \frac{1}{2} \times (n -i + 1) = \frac{n+1}{2}$$

which is independent of where the element is! This is better than $n$. In other words, an adversary would have to place the element in the middle position because he/she does not know which algorithm will be used.