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, butIf 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.

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. :)

不好意思的说,可能是我太笨了我知道B[i]是INDEX 可B[i]=B[i+1]只说明b[i],b[i+1]在相同的区间内, 能说明 a 也在这个区间内吗? a 和 b[i],b[i+1] 没任何关系吧.

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