n/2 = average number of items to search.
Or more precisely (n+1)/2
I could just assert that the answer is n/2, but instead I'll prove it. Since each item has the same probability of being searched for, I'll simulate performing n searches on a list of n items and then calculate the average length of the searches. So I'll have 1 search with a length of 1, another search looks at 2, next search is 3, and so forth and so on until I have the nth search looking at n items. The total number of items looked at for those n searches will be:
1 + 2 + 3 + 4 + ... + n
Now if you want to find the sum of numbers from 1 to n, the formula turns out to be n(n+1)/2
And of course, the average will be that sum divided by n. So we have (n(n+1)/2)/n = (n+1)/2 = n/2 + 1/2
Most people will ignore that constant figure of 1/2 and simply say that if you're doing a linear search of an unsorted list, on average, you'll have to look at half of the list.
