[<<][math][>>][..]
Fri Nov 20 12:09:18 EST 2015
Bisecting intervals with gaps
Find maximum value on a strictly increasing sequence on a circle (last
element in a circular buffer).
This works by successive bisection refinement, picking an initial
interval by arbitrarily picking a point:
(M > L) ? {M,R} : {L,M}
3 4 5 6 7 0 1 2 3
L M R
How to adjust this to be able to bisect ranges with gaps in them
0 1 2 3 4 5 6 7 8 9 index
3 4 5 . 6 7 0 1 2 3 value
L R
The locations of the gaps are not known beforehand. Reading is
expensive.
What to do when index 3 is read?
Guess:
- switch to decision rule:
M >= L ? {M,R} : {L,M}
- copy value from next block
[Reply][About]
[<<][math][>>][..]