Average-case analysis of linear search given that the desired element appears $k$ times
Note
$$
\begin{align*}
E(X)&amp;=\sum_{i=1}^{n-k+1} i \cdot \Pr(X = i)\\
&amp;=\sum_{i=1}^{n-k+1} \sum_{j=1}^i\Pr(X = i)\\
&amp;=\sum_{j=1}^{n-k+1} \sum_{i=j}^{n-k+1}\Pr(X = i)\\
&amp;=\sum_{j=1}^{n-k+1} \Pr(X \ge j),
\end{align*}
$$
and $X\ge j$ means all $x$ are distributed among $A[j],\ldots,A[n]$, so 
$$
\Pr(X \ge j)=\frac{\binom{n-j+1}{k}}{\binom{n}{k}}.
$$
Therefore
$$
E(X)=\sum_{j=1}^{n-k+1} \frac{\binom{n-j+1}{k}}{\binom{n}{k}}=\frac{1}{\binom{n}{k}}\sum_{r=k}^{n}\binom{r}{k}=\frac{1}{\binom{n}{k}}\binom{n+1}{k+1}=\frac{n+1}{k+1}.
$$