# Median

## Input

An ordered sequence $S$ of length $n$ such that a comparison $c$ is defined on the component type $C$ of $S$.

## Output

1. If $n$ is odd, the median is the unique value $x \in \{ S[1],...,S[n]\}$ such that
1. $S[i]\lt x$ for at most $\lfloor n/2 \rfloor$ positions $i$ of $S$ and
2. $S[i]\gt x$ for at most $\lfloor n/2 \rfloor$ positions $i$ of $S$.
2. On the other hand, if $n$ is even, the median is $(x+y)/2$, where $x,y \in \{ S[1],...,S[n]\}$ (let $x \le y$) are the unique values such that
1. $S[i]\lt x$ for at most $\lfloor n/2 \rfloor$ positions $i$ of $S$, and
2. $S[i]\gt y$ for at most $\lfloor n/2 \rfloor$ positions $i$ of $S$.

N/A