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

welcome, andB[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. :)

we discuss it with email bahotherwise it will be lenghy here...