Average case of simple algorithm like binary search These questions is about one of my research. As I am not a computer scientist, formal answering is difficult  to me.

I have a special search algorithm which the explanation here will take a lot of time. However I can explain it shortly by some notations. 

Assume that we have an array of somethings (in my real research they are some cities which they form a path graph) with length $n$. First, we should select one element by some rules( I ignore the rules here) with $O(1)$ time. indeed, according to the rules this element is nearer element to my solution. However, as this rule does not follow a particular order, we can assume that the selection is random.

This element may take tree label, say $L$, $R$ and $M$. The label can be found in $O(1)$ time. If the label is $M$, then we found the solution. Else, if the label is $l$, then we found that this element is not solution and also all elements before it can not be a solution. similarly, this scenario is also correct when the label is $R$, i.e. this element is not solution and also all elements after it can not be a solution. This leads a binary like search algorithm with the difference  that the first element is not the median of array.
we can summarize the above statements as the following algorithm.

Input: An array $A$ with length $n$.
while length(A) &gt; 1 do
 1.  choose an element $k$  (for example, randomly with uniform 
     distribution) with $O(1)$. Find its label with $O(1)$.
 2.If the label is $M$, then stop
 3. else if the label is $l$ then  delete $k$ and all elements before $k$.
 4. else if the label is $r$ then  delete $k$ and all elements after $k$. 
end while


I know that the worst case complexity is  $O(n^2)$ and the best complexity is $O(1)$. What is the average complexity?
The average case time complexity is $O(\log n)$ (with a suitable implementation).  Intuitively, each iteration typically removes a constant factor of the elements from the array.

Here's a more formal analysis. Consider an iteration to be "good" if it removes at least $1/3$ of the elements of the array.  Then an iteration is good with probability $2/3$.  Let $X_1$ denote the number of iterations until the first good iteration; this is a geometric random variable, so its expected value is $1.5$.  Let $X_2$ denote the number of iterations after the first good iteration, until the second good iteration.  Again, the expected value of $X_2$ is $1.5$.  And so on.  Now note that after $j$ good iterations, only a $(2/3)^j$ fraction of elements remain, so after at most $k = \lg_{2/3} n$ good iterations, the array will have only a single element and will terminate immediately.  The total number of iterations is $X_1 + X_2 + X_3 + \cdots + X_k$.  By linearity of expectation, the expected value of this sum is $1.5k$.  Thus the expected number of iterations until this terminates is $1.5 \lg_{2/3} n =  \frac{1.5}{\log(2/3)} \log n = O(\log n)$.

You can implement this so each iteration takes $O(1)$ time.  In particular, you don't actually remove elements in steps 3 and 4; you just keep track of the range of indices of non-removed elements.  That's always a consecutive range, so everything is easy.

In this way, the algorithm takes $O(\log n)$ iterations on average, and $O(1)$ time per iteration, for an average-case running time of $O(\log n)$.

Incidentally, with this implementation, the worst case running time is $O(n)$ rather than $O(\log n)$.  Each iteration of the loop removes at least one element from the array, so there can be at most $n$ iterations of the loop, and each iteration runs in $O(1)$ time, for a total of $O(n)$ worst-case running time.