How does this range follow from this equation?

55 Views Asked by At

How does the range $0\leq i<\frac{n}{2}, \frac{n+1}{2}\leq i<n$ follow from $\left \lfloor \frac{n}{2} \right \rfloor + \left \lfloor \frac{n+1}{2} \right \rfloor = n$?

The source where I read this from(page 2), in order to give some context to the question.

https://arxiv.org/abs/1402.4843

1

There are 1 best solutions below

0
On

In that paper, they deal with finding the middle of an array of length $n$, and the table they give summarizes the various expressions that best express the left half and right half of the array. As a mnemonic for the whole table, they are saying to remember the formula $\lfloor\frac n2\rfloor+\lfloor\frac{n+1}2\rfloor=n$. What this probably means, is that you should (try to) split an array of length $n$ into a left half of length $\lfloor\frac n2\rfloor$, and a right half of length $\lfloor\frac{n+1}2\rfloor$.

Because their arrays have indices from $0$ to $n-1$, that means the left half covers indices from index $0$, to the integer strictly smaller than $\lfloor\frac n2\rfloor$, in other words every integer $i$, $0\le i<\frac n2$. That gives you precisely $\lfloor\frac n2\rfloor$ indices.

For the right half, using the mnemonic you'd go for the indices between $\frac{n+1}2$ until the end of the array, in other words every integer $i$, $\frac{n+1}2\le i<n$. Note that when $n$ is odd, that range does not have $\lfloor\frac{n+1}2\rfloor$ indices. But it is easy to remember the starting index of the right half from the stated equation.

As a somewhat more concrete exemple, assume $n$ is odd, $n=2p+1$. You get $\lfloor\frac n2\rfloor=p$ and $\lfloor\frac{n+1}2\rfloor=p+1$. Using their left/right halves expressions:

  • the left half ranges from $0$ to $p-1$ inclusive, for a total of $p$ indices
  • the right half ranges from $p+1$ to $n-1$ inclusive, for a total of $p$ indices
  • the index $p$ is left out from both halves, and is the central value of the array

Assuming that $n$ is even, $n=2p$, you get $\lfloor\frac n2\rfloor=p=\lfloor\frac{n+1}2\rfloor$.

  • the left half ranges from $0$ to $p-1$ inclusive, for a total of $p$ indices
  • the right half ranges from $p$ to $n-1$ inclusive, for a total of $p$ indices
  • there is no central value in the array