Question

For linear search algorithm,

why is it that on average it takes

(n + 1) / 2 comparisons?

Where does the + 1 come from?

Answer 1

say I have a list of n=4 random numbers on which I do a linear search. On average, we expect to find the number in the middle. This means that half the time, I find the number after 2 comparisons, and half the time I find the number after 3 comparisons. averaging this you get (2+3)/2=5/2=(n+1)/2 comparisons.

Answer 2

It comes from the expected value formula.

x* = (x_1 + x_2 + x_3 + .. + x_n) / n

In this case n is the number of elements, and x_i is the number of comparisons it takes if the ith element is the one you are looking for. In the case of a linear search, x_i = i.
This means sum x_i = n(n+1)/2, and the average is (n+1)/2

See the formula attached.