Average case of simple algorithm like binary search
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.