[<<][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][>>][..]