How to prove that average complexity is N/2 for linear search in the unsorted array All tutorials on algorithms show the complexity for the linear search in the unsorted array in the average case as N/2. I understand that the average case means the items in the list are randomly distributed. 

Can anyone show how I would arrive at N/2 if I have items randomly distributed? Or does it come out of randomly shuffling array bazillion times and recording the number of operations?
First assume input is uniformly distributed. More precisely it is $\frac{n+1}{2}$. When you search for a particular element $x$ in an array of size $n$, that element may be located at the position either $1$, or $2$, $\dots$ or $n$. When we search we check each element in the array and compare it with $x$, and so when we reach $k^\text{th}$ element of the array we have already done $k$ comparisons.

If it is at $1$ then you find it in 1 comparison, if it is at $2$, you find it in 2 comparisons, $\dots$, if it is at $n$ then you do $n$ comparison in order to find it. In order to average it you sum the total number of comparisons $1+2+\dots + n = \frac{(n+1)n}{2}$ and divide it by $n$ (size of the array) resulting in $\frac{n+1}{2}$.


More formal proof:
Assume that the input has uniform probability and the the size of the array is $n$. Let $X$ be a random variable denoting the number of comparisons. Then $p(X=x)$ will denote the probability that we do $x$ comparisons. Since the distribution is uniform, $p(X=x) =\frac{1}{n}$. Once we formally defined our probability distribution now we can calculate the average number of comparisons in the linear search. What we do is compute the expected value 
$$E[X] = \sum_{x=1}^{n}{xp(x)} = \sum_{x=1}^{n}{\frac{x}{n}} = \frac{1}{n}+ \frac{2}{n} + \dots +\frac{n}{n} = \frac{n+1}{2}$$