Arrays and Strings

Table of contents

0-Based Indexing

In computer science, we often use 0-based indexing. Every element in the array is represented as the offset from the beginning.

Some common things that come up when dealing with arrays and strings:

If you have an array of length $n$, the middle element is located at the floor of $n/2$:

$$ \text{mid} = \left\lfloor \frac{n}{2} \right\rfloor $$

Or equivalently, at index $(n-1)/2$.

For odd lengths, this is the exact middle. For even lengths, this is the left middle.

In a range $[l, r]$, the middle element is technically at $(l+r)/2$.

In practice, however this comes with a risk of overflow when $l$ and $r$ are large.

To avoid this, use the following formula:

$$ \text{mid} = l + \left\lfloor \frac{r-l}{2} \right\rfloor $$