Dado un multiconjunto¹⁾ de $n$ valores, se le llama estadístico de orden $k$ al $k$-ésimo elemento más chico. Así, el estadístico de orden 1 es el mínimo elemento, el estadístico de orden 2 es el mínimo elemento entre los que quedan si se borra un elemento mínimo, y así siguiendo, de modo que el estadístico de orden $n$ será simplemente el máximo.

Al estadístico de orden $\frac{n-1}{2}$ se lo llama mediana, y este es especialmente importante ya que separa a los demás valores en “dos partes” iguales: Exactamente $\frac{n-1}{2}$ valores menores o iguales que la mediana, y $\frac{n-1}{2}$ mayores o iguales que la mediana. Si $n$ es par, la mediana no puede partir en dos conjuntos exactamente iguales, así que interesan los estadísticos de orden $\frac{n}{2}$ y $\frac{n}{2}+1$, que son “los dos elementos centrales”. Según el contexto para el cual queramos utilizarla, la mediana en este caso se suele considerar como uno de estos dos valores, o como el promedio de ambos, o como cualquier valor entre uno y otro inclusive.

Es fácil calcular un cierto estadístico de orden ordenando todos los elementos: una vez que tenemos los elementos en un arreglo ordenado, para cada posición $i$ (contando desde 1) se encuentra allí el estadístico de orden $i$. Esto podría tomar en el caso general $O(N \lg N)$ comparaciones, pero calcula todos los estadísticos de orden.

Sin embargo, si buscamos un solo estadístico de orden particular, es posible encontrarlo en $O(N)$, ya que no hace falta ordenar todo el arreglo. En particular, la mediana de un conjunto puede encontrarse con $O(N)$ comparaciones.

: Algoritmo lineal para el cálculo de un estadístico de orden [probabilístico de tipo Las Vegas, salvo adversario maléfico On-Line, el determinista es peor]. La explicación de “Selection” está en el Cormen.

Supongamos que tenemos una larga ruta, con $n$ pueblos en ciertas posiciones. Tenemos que elegir una posición de la ruta para crear allí una oficina de correos, de modo tal que el total de lo que se debe viajar desde cada pueblo hasta la oficina de correos sea lo menor posible.

El total es justamente la suma, sobre todos los pueblos, de la distancia entre el pueblo y la oficina. Más precisamente, si el pueblo $i$ está en el kilómetro $p_i$ de la ruta, y ubicamos la oficina de correos en $x$, entonces el total de kilómetros de viaje será $\sum_{i=1}^n{|p_i - x|}$. Lo que buscamos es el $x$ que minimice esta cuenta.

Como ejemplo de búsqueda ternaria, vimos que la función anterior resulta ser convexa y por lo tanto unimodal, así que con búsqueda binaria o ternaria se puede encontrar el valor mínimo y el kilómetro óptimo (valor de $x$) donde ubicar la oficina.

Sin embargo, es posible dar una solución más elegante, que permite entender mejor lo que está pasando y que a veces es más útil para razonar o para resolver problemas más complejos: resulta que el valor óptimo de $x$ es la mediana ²⁾. La explicación se basa en el dibujo interactivo que se puede ver aquí. Como la distancia total es la suma de las “barritas” desde $x$ hasta los puntos, cuando hay más barritas de un lado que del otro, es posible bajar la distancia total moviendo $x$ en esa dirección. Por lo tanto, necesariamente el mejor valor posible tendrá que tener igual cantidad barritas saliendo hacia cada lado, para que no se puede mejorar moviendo $x$. Y eso ocurre cuando $x$ es la mediana de los puntos $p_i$.

Un problema relacionado con esta última idea (pero que involucra más que solamente eso) es el problema Post Office de la IOI 2003.

Otro problema relacionado con la mediana en esa misma IOI es Median Strength

Una variante de la misma idea puede ocurrir cuando los “pueblos” tienen un peso $w_i$ (podría ser su cantidad de habitantes), de forma que nos interesa optimizar $\sum_{i=1}^n{w_i|p_i - x|}$. En este caso, lo que notamos es que la cuenta es la misma que en el problema normal sin pesos, si tuviéramos $w_i$ copias del pueblo $p_i$³⁾. Entonces, el lugar óptimo es la “mediana de los pesos”, es decir, la posición de aquel pueblo que reparta los pesos totales a izquierda y derecha lo más parejo posible.

Otros estadísticos de orden nos darían el óptimo, en lugar de la mediana, si trabajamos con una distancia “asimétrica”. Por ejemplo, supongamos que la ruta está sobre la ladera de una montaña, y a medida que avanzan los kilómetros en la ruta, esta siempre asciende la montaña. De esta forma, es natural considerar más costosos los recorridos subiendo que los recorridos bajando. Si suponemos que solo nos interesa analizar el costo para los viajes del pueblo a la oficina de correos y no el de la vuelta⁴⁾, la “distancia” entre un pueblo $p_i$ y la oficina de correos será $p_i-x$, si $ x \leq p_i$, o bien $C(x-p_i)$ si $p_i \leq x$, siendo $C$ un factor de costo “adicional” por subir la montaña.

La mediana da el óptimo con $C=1$. Para otros valores de $C$, por el mismo argumento de analizar cómo cambia el costo al mover $x$, el óptimo se alcanzará cuando hacia arriba haya $C$ veces la cantidad de pueblos que hacia abajo, pues si no fuera así, mover $x$ en una de las dos direcciones reduce el costo total. Esto significa que el $x$ óptimo es el pueblo que deja $\frac{n}{1+C}$ pueblos a su izquierda, es decir, el estadístico de orden $\frac{n}{1+C}$ entre las posiciones de los pueblos.