er,The worst case performance is very difficult to improve, which is lg(n)
You can improve the averge case performance, by the following data structure:
(I suggested)
Divide the [0, 1) into 64 equally spanned intervels,by b1=1/64, b2=2/64, ...
Record into B which interval of A that bi belongs to.
If B[i]=B[i+1], then you meet a nice case when the randon number fall into
b[i], b[i+1], otherwise, you maybe need to divide B[i] recursively.
To implement this will be tedious. You are can compute that the average
case for this datastructure will be O(1).
Hope that will be helpful
thanx very much for sc2's suggestion, but
If B[i]=B[i+1], it can only be deduced that the width for one of the subintervals A[j+1]-A[j]>1/64. But which subinterval the random number a resides is independent of the width of the subinterval, am i right?
Actually the matrix A is a known quantity, which determines how the interval [0,1) is divided into subintervals, the widths of which might not be the same. And the random number a is the "true" variable.
Actually the matrix A is a known quantity, which determines how the interval [0,1) is divided into subintervals, the widths of which might not be the same. And the random number a is the "true" variable.
Huasing Association 1999 - 2013