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