Average case of simple algorithm like binary search

Question

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) > 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?