0

Say I have a range r from a - b, $a\in \mathbb{R}$ and $b\in \mathbb{R} $.

Then, I have an integer i.

Now, if I were to break the range in half, decrease i, then continue breaking the remaining ranges in half from left to right, decreasing i until i is 0, where would the next splitting point be if I were to continue?

For example, say I have r=0-360 and i=7.

first, I'd split r in half at 180 into $r_1 = 0-180$ and $r_2 = 0-180$ then, for i = 2, I'd split $r_1$ into $r_3 = 0-90$ and $r_4 = 90-180$. For i = 3, I'd split $r_2$ into $r_5 = 180-270$ and $r_6 = 270-360$.

Eventually, for i=7, I'd get 315.

I can think of a recursive function, like this one:

$ f_{(a\rightarrow b) , i}(j) = \left\{ \begin{array}{ll1} f_{(a\rightarrow a+\frac{b-a}2) , i}(C_l(j)) \vee f_{(a+\frac{b-a}2 \rightarrow b) , i}(C_r(j)) & \mbox{if $j < i$}\\ a+\frac{b-a}2 & \mbox{if $j = i$}\\ false & \mbox{if $j > i$}\end{array} \right. $

where $C_l(j)$ and $C_r(j)$ calculate the left and right child of j respectively on a binary tree ordered like:

0

1,2

3,4,5,6

etc.

Also, the initial value of j is 0.

 

...What would that be as a non-recursive algorithm though?

SimLeek
  • 3

1 Answers1

0

Let $N_{u, v}$ represent the $v^\text{th}$ subrange node in the tree located at depth $u$, where $u$ and $v$ are $0$-based indices. Then: $$ N_{u, v} = \left[a + v\left( \frac{b - a}{2^u} \right) \qquad\text{to}\qquad a + (v + 1)\left( \frac{b - a}{2^u} \right) \right] $$

For example, your $r_4$ corresponds to: $$ N_{2, 1} = \left[0 + 1\left( \frac{360 - 0}{2^2} \right) \qquad\text{to}\qquad 0 + (1 + 1)\left( \frac{360 - 0}{2^2} \right) \right] = [90 \text{ to } 180] $$

Adriano
  • 41,576
  • Well, since the question was in terms of a single indice i on the binary tree I mentioned, I'd like to add that you can get u and v from i with the equations u=floor(log_2(i+1)) and v=i-2^u +1. – SimLeek Mar 21 '16 at 22:17