Big O analysis for problem where number of items searched is unknown
Big-O gives the upper bound function of any analysis. For an algorithm you could represent all (Worst, Average, Best) cases in Big-O notation.

In your case,


Worst case: The required element is not present in the array (or is the last element of the array) : O(M)
Best case: The element is found in the first position itself: O(1)
Average case: Average of all possible case, i.e., the average time complexity of the cases where the element could be found at each possible position:


$$
\begin{align}
 = \frac{(1 + 2 + 3 + ... + M)}{M} \\
 = \frac{M(M + 1)/2}{M} \\
 = (M + 1)/2\\
= O(M)
\end{align}
$$

The average case is what you're looking for, which again O(M) only.