Does randomness buy us anything inside P? Let $\mathsf{BPTIME}(f(n))$ be the class of the decision problems having a bounded two-sided error randomized algorithm running in time $O(f(n))$. 

Do we know of any problem $Q \in \mathsf{P}$ such that $Q \in \mathsf{BPTIME}(n^k)$ but $Q \not \in \mathsf{DTIME}(n^k)$? 
Is its non-existence proven?

This question was asked on cs.SE here, but did not get a satisfactory answer.
Problem: An array $A[1..2n]$ consists of $n$ 1s and $n$ 0s. Find an $i$ such that $A[i]$ is 1. 

You are allowed to query 'Which number is present in $A[i]$'? Each query takes constant time. 

Solution: 
Randomized Algorithm: Pick a random index $i$ and check if $A[i]$ is 1. Expected number of queries is 2, but any deterministic algorithm must make at least $n$ queries. Therefore, the randomized upper bound is strictly better than the deterministic lower bound in this model.

This is an example from query complexity which Tsuyoshi was referring to in the comment.