Minimization of convex stochastic values

Minimization of convex stochastic values

I have a variable of equidistant values (suppose values=0:1e-3:1). I want
to get the value and its correspondent index from values which is closest
to a uniformly random value (suppose x=rand).
I could do [value,vIdx]=min(abs(values-x)), which would be the simplest
minimization I could do. Unfortunately the min function won't take
advantage from one property from the data, that is to be convex. I don't
need to search all indexes, because as soon as find an index that is no
more lesser than the previous I've found the global minimum. Said that, I
don't want to substitute the matlab min function for a loop that would be
slower depending on how distant it is from the value I will start. There
are many methods that could be used, as the golden section, but I am not
sure if using matlab fmincon would be faster than the min method.
Does anyone has any hints/ideas how to get the required value faster than
using the described min method? I'll check the time performance when I
have time, but if someone knows a good answer a priori, please let me
know.