searching algorithm enquiry请教PROGRAMMING高手们:
If i divide the interval I=[0,1) into, say, 64 subintervals, and recode the 64 left pts into an Array A[0:63] in ascending order, how can I decide which interval a random number a (- [0,1) is in with the LEAST possible loopings?
The method I use now is : start from the centre A[33], check if a>A[33]. if yes, check the centre of the upper half
if a>A[49]; else check centre of the lower half if a>A[17]. So on and so forth, just like the idea of a binary ADC converter. but i need 6 looping interation in order to get the answer. Any one knows faster method than this?
[wangye (7-27 22:56, Long long ago)]
[ 传统版 |
sForum ][登录后回复]1楼
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[sc2 (7-28 11:06, Long long ago)]
[ 传统版 |
sForum ][登录后回复]2楼
(引用 sc2:er,The worst case performance is very difficult to improve, which is lg(n)
You can improve the averge case performance, by the ...)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. [wangye (7-28 20:34, Long long ago)]
[ 传统版 |
sForum ][登录后回复]3楼
(引用 wangye: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...)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. :)[sc2 (7-29 10:57, Long long ago)]
[ 传统版 |
sForum ][登录后回复]4楼
(引用 sc2: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 b...)不好意思的说,可能是我太笨了我知道B[i]是INDEX
可B[i]=B[i+1]只说明b[i],b[i+1]在相同的区间内, 能说明 a 也在这个区间内吗? a 和 b[i],b[i+1] 没任何关系吧.[wangye (7-29 21:55, Long long ago)]
[ 传统版 |
sForum ][登录后回复]5楼
(引用 wangye:不好意思的说,可能是我太笨了我知道B[i]是INDEX 可B[i]=B[i+1]只说明b[i],b[i+1]在相同的区间内, 能说明 a 也在这个区间内吗? a 和 b[i]...)we discuss it with email bahotherwise it will be lenghy here...[sc2 (7-30 11:39, Long long ago)] [ 传统版 | sForum ][登录后回复]6楼
(引用 sc2:we discuss it with email bahotherwise it will be lenghy here...)no problemlaowangye@hotmail.com[wangye (7-30 14:08, Long long ago)] [ 传统版 | sForum ][登录后回复]7楼