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, and
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. :)
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. :)
Huasing Association 1999 - 2013