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

B[i] records the A's interval ID(the index, not the real value).
and B's size is not necesarily to be 64, say, can be 200.

if B[i]=B[i+1], then B[i] is the value u want.
otherwise B[i+1]>B[i], you may just sub-divide the range [i/64, (i+1)/64).
Otherwise, you can just do a liear scan from A[B[i]] to A[B[i+1]],
the expect number of intervals tp be scanned
should be very small (O(1)). The worst case can be large as larger as
A's size (you can do a binary search again (O(lgn)),
but the overhead will be large).

Yup, A is random and sorted in increasing order?!, if u want to find
the right interval by comparison, the worst case bound is O(lgn), and
hard to improve. :)

otherwise it will be lenghy here...