chapter03.tex

\chapter{Ordenamiento}

\index{ordenamiento}

\key{Ordenamiento}
es un problema fundamental de diseño de algoritmos.
Muchos algoritmos eficientes
utilizan el ordenamiento como una subrutina,
porque a menudo es más fácil procesar
datos si los elementos están en orden.

Por ejemplo, el problema ''¿contiene un arreglo
dos elementos iguales?'' es fácil de resolver usando el ordenamiento.
Si el arreglo contiene dos elementos iguales,
estos estarán uno al lado del otro después del ordenamiento,
por lo que es fácil encontrarlos.
Además, el problema ''¿cuál es el elemento más frecuente
en un arreglo?'' se puede resolver de manera similar.

Hay muchos algoritmos para el ordenamiento, y estos son
también buenos ejemplos de cómo aplicar
diferentes técnicas de diseño de algoritmos.
Los algoritmos generales de ordenamiento eficientes
funcionan en tiempo $O(n \log n)$,
y muchos algoritmos que utilizan el ordenamiento
como una subrutina también
tienen esta complejidad de tiempo.

\section{Teoría de ordenamiento}

El problema básico en el ordenamiento es el siguiente:
\begin{framed}
\noindent
Dado un arreglo que contiene $n$ elementos,
tu tarea es ordenar los elementos
en orden creciente.
\end{framed}
\noindent
Por ejemplo, el arreglo
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$8$};
\node at (3.5,0.5) {$2$};
\node at (4.5,0.5) {$9$};
\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$6$};
\end{tikzpicture}
\end{center}
será como sigue después del ordenamiento:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$2$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$3$};
\node at (4.5,0.5) {$5$};
\node at (5.5,0.5) {$6$};
\node at (6.5,0.5) {$8$};
\node at (7.5,0.5) {$9$};
\end{tikzpicture}
\end{center}

\subsubsection{Algoritmos $O(n^2)$}

\index{ordenamiento por burbuja}

Los algoritmos simples para ordenar un arreglo
funcionan en tiempo $O(n^2)$.
Tales algoritmos son cortos y generalmente
constan de dos bucles anidados.
Un famoso algoritmo de ordenamiento en tiempo $O(n^2)$
es \key{ordenamiento por burbuja} donde los elementos
''burbujean'' en el arreglo de acuerdo con sus valores.

El ordenamiento por burbuja consta de $n$ rondas.
En cada ronda, el algoritmo itera a través
de los elementos del arreglo.
Cuando se encuentran dos elementos consecutivos
que no están en el orden correcto,
el algoritmo los intercambia.
El algoritmo se puede implementar de la siguiente manera:
\begin{lstlisting}
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n-1; j++) {
        if (array[j] > array[j+1]) {
            swap(array[j],array[j+1]);
        }
    }
}
\end{lstlisting}

Después de la primera ronda del algoritmo,
el elemento más grande estará en la posición correcta,
y en general, después de $k$ rondas, los $k$ elementos más grandes
estarán en las posiciones correctas.
Por lo tanto, después de $n$ rondas, todo el arreglo
estará ordenado.

Por ejemplo, en el arreglo

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);

\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$8$};
\node at (3.5,0.5) {$2$};
\node at (4.5,0.5) {$9$};
\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$6$};
\end{tikzpicture}
\end{center}

\noindent
la primera ronda de ordenamiento por burbuja intercambia elementos
de la siguiente manera:

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$8$};
\node at (4.5,0.5) {$9$};
\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$6$};

\draw[thick,<->] (3.5,-0.25) .. controls (3.25,-1.00) and (2.75,-1.00) .. (2.5,-0.25);
\end{tikzpicture}
\end{center}

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$8$};
\node at (4.5,0.5) {$2$};
\node at (5.5,0.5) {$9$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$6$};

\draw[thick,<->] (5.5,-0.25) .. controls (5.25,-1.00) and (4.75,-1.00) .. (4.5,-0.25);
\end{tikzpicture}
\end{center}

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$8$};
\node at (4.5,0.5) {$2$};
\node at (5.5,0.5) {$5$};
\node at (6.5,0.5) {$9$};
\node at (7.5,0.5) {$6$};

\draw[thick,<->] (6.5,-0.25) .. controls (6.25,-1.00) and (5.75,-1.00) .. (5.5,-0.25);
\end{tikzpicture}
\end{center}

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$8$};
\node at (4.5,0.5) {$2$};
\node at (5.5,0.5) {$5$};
\node at (6.5,0.5) {$6$};
\node at (7.5,0.5) {$9$};

\draw[thick,<->] (7.5,-0.25) .. controls (7.25,-1.00) and (6.75,-1.00) .. (6.5,-0.25);
\end{tikzpicture}
\end{center}

\subsubsection{Inversiones}

\index{inversión}
La ordenación por burbuja es un ejemplo de un algoritmo de ordenación que siempre intercambia elementos \emph{consecutivos} en la matriz.
Resulta que la complejidad temporal de este tipo de algoritmo es \emph{siempre}
al menos $O(n^2)$, porque en el peor caso,
se necesitan $O(n^2)$ intercambios para ordenar la matriz.

Un concepto útil al analizar algoritmos de ordenación es una \key{inversión}:
un par de elementos de la matriz
$(\texttt{array}[a],\texttt{array}[b])$ tal que
$a<b$ y $\texttt{array}[a]>\texttt{array}[b]$,
es decir, los elementos están en el orden incorrecto.
Por ejemplo, la matriz
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$2$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$6$};
\node at (4.5,0.5) {$3$};
\node at (5.5,0.5) {$5$};
\node at (6.5,0.5) {$9$};
\node at (7.5,0.5) {$8$};
\end{tikzpicture}
\end{center}
tiene tres inversiones: $(6,3)$, $(6,5)$ y $(9,8)$.
El número de inversiones indica
cuánto trabajo se necesita para ordenar la matriz.
Una matriz está completamente ordenada cuando
no hay inversiones.
Por otro lado, si los elementos de la matriz
están en orden inverso,
el número de inversiones es el mayor posible:
\[1+2+\cdots+(n-1)=\frac{n(n-1)}{2} = O(n^2)\]

Intercambiar un par de elementos consecutivos que estén
en el orden incorrecto elimina exactamente una inversión
de la matriz.
Por lo tanto, si un algoritmo de ordenación solo puede
intercambiar elementos consecutivos, cada intercambio elimina
como máximo una inversión, y la complejidad temporal
del algoritmo es al menos $O(n^2)$.

\subsubsection{$O(n \log n)$ algoritmos}

\index{merge sort}

Es posible ordenar una matriz de forma eficiente
en tiempo $O(n \log n)$ usando algoritmos
que no se limitan a intercambiar elementos consecutivos.
Un algoritmo de este tipo es \key{merge sort}\footnote{Según \cite{knu983},
la ordenación por mezcla fue inventada por J. von Neumann en 1945.},
que se basa en la recursión.

Merge sort ordena una submatriz \texttt{array}$[a \ldots b]$ de la siguiente manera:

\begin{enumerate}
\item Si $a=b$, no hacer nada, porque la submatriz ya está ordenada.
\item Calcular la posición del elemento del medio: $k=\lfloor (a+b)/2 \rfloor$.
\item Ordenar recursivamente la submatriz \texttt{array}$[a \ldots k]$.
\item Ordenar recursivamente la submatriz \texttt{array}$[k+1 \ldots b]$.
\item \emph{Combinar} las submatrices ordenadas \texttt{array}$[a \ldots k]$ y
\texttt{array}$[k+1 \ldots b]$
en una submatriz ordenada \texttt{array}$[a \ldots b]$.
\end{enumerate}

Merge sort es un algoritmo eficiente, porque
reduce a la mitad el tamaño de la submatriz en cada paso.
La recursión consta de $O(\log n)$ niveles,
y el procesamiento de cada nivel lleva $O(n)$ tiempo.
Combinar las submatrices \texttt{array}$[a \ldots k]$ y \texttt{array}$[k+1 \ldots b]$
es posible en tiempo lineal, porque ya están ordenadas.

Por ejemplo, considere la ordenación de la siguiente matriz:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$6$};
\node at (3.5,0.5) {$2$};
\node at (4.5,0.5) {$8$};
\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$9$};
\end{tikzpicture}
\end{center}

La matriz se dividirá en dos submatrices
de la siguiente manera:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (4,1);
\draw (5,0) grid (9,1);

\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$6$};
\node at (3.5,0.5) {$2$};

\node at (5.5,0.5) {$8$};
\node at (6.5,0.5) {$2$};
\node at (7.5,0.5) {$5$};
\node at (8.5,0.5) {$9$};
\end{tikzpicture}
\end{center}

Entonces, las submatrices se ordenarán recursivamente
de la siguiente manera:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (4,1);
\draw (5,0) grid (9,1);

\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$2$};
\node at (2.5,0.5) {$3$};
\node at (3.5,0.5) {$6$};

\node at (5.5,0.5) {$2$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$8$};
\node at (8.5,0.5) {$9$};
\end{tikzpicture}
\end{center}

Finalmente, el algoritmo combina las ordenadas
submatrices y crea la matriz ordenada final:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$2$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$3$};
\node at (4.5,0.5) {$5$};
\node at (5.5,0.5) {$6$};
\node at (6.5,0.5) {$8$};
\node at (7.5,0.5) {$9$};
\end{tikzpicture}
\end{center}

\subsubsection{Límite inferior de ordenación}

¿Es posible ordenar una matriz más rápido
que en tiempo $O(n \log n)$?
Resulta que esto \emph{no} es posible
cuando nos limitamos a algoritmos de ordenación
que se basan en la comparación de elementos de la matriz.

El límite inferior para la complejidad temporal
se puede probar considerando la ordenación
como un proceso donde cada comparación de dos elementos
proporciona más información sobre el contenido de la matriz.
El proceso crea el siguiente árbol:

\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) rectangle (3,1);
\node at (1.5,0.5) {$x < y?$};

\draw[thick,->] (1.5,0) -- (-2.5,-1.5);
\draw[thick,->] (1.5,0) -- (5.5,-1.5);
\draw (-4,-2.5) rectangle (-1,-1.5);
\draw (4,-2.5) rectangle (7,-1.5);
\node at (-2.5,-2) {$x < y?$};
\node at (5.5,-2) {$x < y?$};

\draw[thick,->] (-2.5,-2.5) -- (-4.5,-4);
\draw[thick,->] (-2.5,-2.5) -- (-0.5,-4);
\draw[thick,->] (5.5,-2.5) -- (3.5,-4);
\draw[thick,->] (5.5,-2.5) -- (7.5,-4);

\draw (-6,-5) rectangle (-3,-4);
\draw (-2,-5) rectangle (1,-4);
\draw (2,-5) rectangle (5,-4);
\draw (6,-5) rectangle (9,-4);
\node at (-4.5,-4.5) {$x < y?$};
\node at (-0.5,-4.5) {$x < y?$};
\node at (3.5,-4.5) {$x < y?$};
\node at (7.5,-4.5) {$x < y?$};

\draw[thick,->] (-4.5,-5) -- (-5.5,-6);
\draw[thick,->] (-4.5,-5) -- (-3.5,-6);
\draw[thick,->] (-0.5,-5) -- (0.5,-6);
\draw[thick,->] (-0.5,-5) -- (-1.5,-6);
\draw[thick,->] (3.5,-5) -- (2.5,-6);
\draw[thick,->] (3.5,-5) -- (4.5,-6);
\draw[thick,->] (7.5,-5) -- (6.5,-6);
\draw[thick,->] (7.5,-5) -- (8.5,-6);
\end{tikzpicture}
\end{center}

Aquí ''$x<y?$'' significa que algunos elementos
$x$ e $y$ se comparan.
Si $x<y$, el proceso continúa a la izquierda,
y de lo contrario a la derecha.
Los resultados del proceso son las posibles
formas de ordenar la matriz, un total de $n!$ maneras.
Por esta razón, la altura del árbol
debe ser al menos
\[ \log_2(n!) = \log_2(1)+\log_2(2)+\cdots+\log_2(n).\]
Obtenemos un límite inferior para esta suma
eligiendo los últimos $n/2$ elementos y
cambiando el valor de cada elemento a $\log_2(n/2)$.
Esto produce una estimación
\[ \log_2(n!) \ge (n/2) \cdot \log_2(n/2),\]
por lo que la altura del árbol y el mínimo
número posible de pasos en un ordenamiento
algoritmo en el peor de los casos
es al menos $n \log n$.

\subsubsection{Ordenación por conteo}

\index{ordenación por conteo}

El límite inferior $n \log n$ no se aplica a
algoritmos que no comparan elementos de la matriz
sino que utilizan alguna otra información.
Un ejemplo de tal algoritmo es
\key{ordenación por conteo} que ordena una matriz en
tiempo $O(n)$ asumiendo que cada elemento de la matriz
es un entero entre $0 \ldots c$ y $c=O(n)$.

El algoritmo crea una matriz de \emph{contabilidad},
cuyos índices son elementos de la matriz original.
El algoritmo itera a través de la matriz original
y calcula cuántas veces aparece cada elemento
en la matriz.
\newpage

Por ejemplo, la matriz
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (8,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$3$};
\node at (2.5,0.5) {$6$};
\node at (3.5,0.5) {$9$};
\node at (4.5,0.5) {$9$};
\node at (5.5,0.5) {$3$};
\node at (6.5,0.5) {$5$};
\node at (7.5,0.5) {$9$};
\end{tikzpicture}
\end{center}
corresponde a la siguiente matriz de contabilidad:
\begin{center}
\begin{tikzpicture}[scale=0.7]
\draw (0,0) grid (9,1);
\node at (0.5,0.5) {$1$};
\node at (1.5,0.5) {$0$};
\node at (2.5,0.5) {$2$};
\node at (3.5,0.5) {$0$};
\node at (4.5,0.5) {$1$};
\node at (5.5,0.5) {$1$};
\node at (6.5,0.5) {$0$};
\node at (7.5,0.5) {$0$};
\node at (8.5,0.5) {$3$};

\footnotesize

\node at (0.5,1.5) {$1$};
\node at (1.5,1.5) {$2$};
\node at (2.5,1.5) {$3$};
\node at (3.5,1.5) {$4$};
\node at (4.5,1.5) {$5$};
\node at (5.5,1.5) {$6$};
\node at (6.5,1.5) {$7$};
\node at (7.5,1.5) {$8$};
\node at (8.5,1.5) {$9$};
\end{tikzpicture}
\end{center}

Por ejemplo, el valor en la posición 3
en la matriz de contabilidad es 2,
porque el elemento 3 aparece 2 veces
en la matriz original.

La construcción de la matriz de contabilidad
toma tiempo $O(n)$. Después de esto, la matriz ordenada
se puede crear en tiempo $O(n)$ porque
el número de ocurrencias de cada elemento se puede recuperar
de la matriz de contabilidad.
Por lo tanto, la complejidad temporal total de la contabilidad
ordenar es $O(n)$.

La ordenación por conteo es un algoritmo muy eficiente
pero solo se puede utilizar cuando la constante $c$
es lo suficientemente pequeña, para que los elementos de la matriz puedan
usarse como índices en la matriz de contabilidad.

\section{Ordenación en C++}

\index{sort@\texttt{sort}}

Casi nunca es una buena idea usar
un algoritmo de ordenación hecho en casa
en un concurso, porque hay buenos
implementaciones disponibles en lenguajes de programación.
Por ejemplo, la biblioteca estándar de C++ contiene
la función \texttt{sort} que se puede utilizar fácilmente para
ordenar matrices y otras estructuras de datos.

Hay muchos beneficios en usar una función de biblioteca.
Primero, ahorra tiempo porque no hay necesidad de
implementar la función.
En segundo lugar, la implementación de la biblioteca es
ciertamente correcta y eficiente: no es probable
que una función de ordenación hecha en casa sea mejor.

En esta sección veremos cómo usar la función \texttt{sort} de C++.
El siguiente código ordena un vector en orden creciente:
\begin{lstlisting}
vector<int> v = {4,2,5,3,5,8,3};
sort(v.begin(),v.end());
\end{lstlisting}
Después de la ordenación, el contenido del vector será
$[2,3,3,4,5,5,8]$.
El orden de clasificación predeterminado es creciente,
pero un orden inverso es posible de la siguiente manera:
\begin{lstlisting}
sort(v.rbegin(),v.rend());
\end{lstlisting}
Se puede ordenar una matriz ordinaria de la siguiente manera:
\begin{lstlisting}
int n = 7; // tamano del array
int a[] = {4,2,5,3,5,8,3};
sort(a,a+n);
\end{lstlisting}

\newpage
El siguiente código ordena la cadena \texttt{s}:
\begin{lstlisting}
string s = "monkey";
sort(s.begin(), s.end());
\end{lstlisting}
Ordenar una cadena significa que los caracteres
de la cadena están ordenados.
Por ejemplo, la cadena ''monkey'' se convierte en ''ekmnoy''.

\subsubsection{Operadores de comparación}

\index{operador de comparación}

La función \texttt{sort} requiere que
se defina un \key{operador de comparación} para el tipo de datos
de los elementos a ordenar.
Al ordenar, este operador se utilizará
cada vez que sea necesario averiguar el orden de dos elementos.

La mayoría de los tipos de datos de C++ tienen un operador de comparación integrado,
y los elementos de esos tipos se pueden ordenar automáticamente.
Por ejemplo, los números se ordenan según sus valores
y las cadenas se ordenan en orden alfabético.

\index{pair@\texttt{pair}}

Los pares (\texttt{pair}) se ordenan principalmente según sus
primeros elementos (\texttt{first}).
Sin embargo, si los primeros elementos de dos pares son iguales,
se ordenan según sus segundos elementos (\texttt{second}):
\begin{lstlisting}
vector<pair<int,int>> v;
v.push_back({1,5});
v.push_back({2,3});
v.push_back({1,2});
sort(v.begin(), v.end());
\end{lstlisting}
Después de esto, el orden de los pares es
$(1,2)$, $(1,5)$ y $(2,3)$.

\index{tuple@\texttt{tuple}}

De manera similar, las tuplas (\texttt{tuple})
se ordenan principalmente por el primer elemento,
secundariamente por el segundo elemento, etc.\footnote{Tenga en cuenta que en algunos compiladores más antiguos,
la función \texttt{make\_tuple} debe utilizarse para crear una tupla en lugar de
llaves (por ejemplo, \texttt{make\_tuple(2,1,4)} en lugar de \texttt{\{2,1,4\}}).}:
\begin{lstlisting}
vector<tuple<int,int,int>> v;
v.push_back({2,1,4});
v.push_back({1,5,3});
v.push_back({2,1,3});
sort(v.begin(), v.end());
\end{lstlisting}
Después de esto, el orden de las tuplas es
$(1,5,3)$, $(2,1,3)$ y $(2,1,4)$.

\subsubsection{Estructuras definidas por el usuario}

Las estructuras definidas por el usuario no tienen un operador de comparación
automáticamente.
El operador debe definirse dentro
de la estructura como una función
\texttt{operator<},
cuyo parámetro es otro elemento del mismo tipo.
El operador debe devolver \texttt{true}
si el elemento es menor que el parámetro,
y \texttt{false} en caso contrario.

Por ejemplo, la siguiente estructura \texttt{P}
contiene las coordenadas x e y de un punto.
El operador de comparación se define de modo que
los puntos se ordenen principalmente por la coordenada x
y secundariamente por la coordenada y.

\begin{lstlisting}
struct P {
    int x, y;
    bool operator<(const P &p) {
        if (x != p.x) return x < p.x;
        else return y < p.y;
    }
};
\end{lstlisting}

\subsubsection{Funciones de comparación}

\index{función de comparación}

También es posible dar una externa
\key{función de comparación} a la función \texttt{sort}
como una función de devolución de llamada.
Por ejemplo, la siguiente función de comparación \texttt{comp}
ordena las cadenas principalmente por longitud y secundariamente
por orden alfabético:

\begin{lstlisting}
bool comp(string a, string b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
}
\end{lstlisting}
Ahora un vector de cadenas se puede ordenar de la siguiente manera:
\begin{lstlisting}
sort(v.begin(), v.end(), comp);
\end{lstlisting}

\section{Búsqueda binaria}

\index{búsqueda binaria}

Un método general para buscar un elemento
en un array es usar un bucle \texttt{for}
que itera a través de los elementos del array.
Por ejemplo, el siguiente código busca
un elemento $x$ en un array:

\begin{lstlisting}
for (int i = 0; i < n; i++) {
    if (array[i] == x) {
        // x encontrado en el indice i
    }
}
\end{lstlisting}

La complejidad temporal de este enfoque es $O(n)$,
porque en el peor de los casos, es necesario comprobar
todos los elementos del array.
Si el orden de los elementos es arbitrario,
este es también el mejor enfoque posible, porque
no hay información adicional disponible sobre dónde
en el array debemos buscar el elemento $x$.

Sin embargo, si el array está \emph{ordenado},
la situación es diferente.
En este caso, es posible realizar la
búsqueda mucho más rápido, porque el orden de los
elementos en el array guía la búsqueda.
El siguiente algoritmo de \key{búsqueda binaria}
busca eficientemente un elemento en un array ordenado
en $O(\log n)$ tiempo.

\subsubsection{Método 1}
La forma usual de implementar la búsqueda binaria
se asemeja a buscar una palabra en un diccionario.
La búsqueda mantiene una región activa en la matriz,
que inicialmente contiene todos los elementos de la matriz.
Luego, se realiza una serie de pasos,
cada uno de los cuales reduce a la mitad el tamaño de la región.

En cada paso, la búsqueda verifica el elemento del medio
de la región activa.
Si el elemento del medio es el elemento objetivo,
la búsqueda termina.
De lo contrario, la búsqueda continúa recursivamente
a la mitad izquierda o derecha de la región,
dependiendo del valor del elemento del medio.

La idea anterior se puede implementar de la siguiente manera:
\begin{lstlisting}
int a = 0, b = n-1;
while (a <= b) {
    int k = (a+b)/2;
    if (array[k] == x) {
        // x encontrado en el indice k
    }
    if (array[k] > x) b = k-1;
    else a = k+1;
}
\end{lstlisting}

En esta implementación, la región activa es $a \ldots b$,
y inicialmente la región es $0 \ldots n-1$.
El algoritmo reduce a la mitad el tamaño de la región en cada paso,
por lo que la complejidad temporal es $O(\log n)$.

\subsubsection{Método 2}

Un método alternativo para implementar la búsqueda binaria
se basa en una forma eficiente de iterar a través de
los elementos de la matriz.
La idea es hacer saltos y reducir la velocidad
cuando nos acercamos al elemento objetivo.

La búsqueda recorre la matriz de izquierda a
derecha, y la longitud de salto inicial es $n/2$.
En cada paso, la longitud del salto se reducirá a la mitad:
primero $n/4$, luego $n/8$, $n/16$, etc., hasta
que finalmente la longitud sea 1.
Después de los saltos, o bien se ha encontrado el elemento objetivo
o sabemos que no aparece en la matriz.

El siguiente código implementa la idea anterior:
\begin{lstlisting}
int k = 0;
for (int b = n/2; b >= 1; b /= 2) {
    while (k+b < n && array[k+b] <= x) k += b;
}
if (array[k] == x) {
    // x encontrado en el indice k
}
\end{lstlisting}

Durante la búsqueda, la variable $b$
contiene la longitud del salto actual.
La complejidad temporal del algoritmo es $O(\log n)$,
porque el código en el bucle \texttt{while}
se ejecuta como máximo dos veces para cada longitud de salto.

\subsubsection{Funciones de C++}

La biblioteca estándar de C++ contiene las siguientes funciones
que se basan en la búsqueda binaria y funcionan en tiempo logarítmico:

\begin{itemize}
\item \texttt{lower\_bound} devuelve un puntero al
primer elemento de la matriz cuyo valor es al menos $x$.
\item \texttt{upper\_bound} devuelve un puntero al
primer elemento de la matriz cuyo valor es mayor que $x$.
\item \texttt{equal\_range} devuelve ambos punteros anteriores.
\end{itemize}

Las funciones asumen que la matriz está ordenada.
Si no existe tal elemento, el puntero apunta a
el elemento después del último elemento de la matriz.
Por ejemplo, el siguiente código descubre si
una matriz contiene un elemento con valor $x$:

\begin{lstlisting}
auto k = lower_bound(array,array+n,x)-array;
if (k < n && array[k] == x) {
    // x encontrado en el indice k
}
\end{lstlisting}

Luego, el siguiente código cuenta el número de elementos
cuyo valor es $x$:

\begin{lstlisting}
auto a = lower_bound(array, array+n, x);
auto b = upper_bound(array, array+n, x);
cout << b-a << "\n";
\end{lstlisting}

Usando \texttt{equal\_range}, el código se vuelve más corto:

\begin{lstlisting}
auto r = equal_range(array, array+n, x);
cout << r.second-r.first << "\n";
\end{lstlisting}

\subsubsection{Encontrar la solución más pequeña}

Un uso importante de la búsqueda binaria es
encontrar la posición donde cambia el valor de una \emph{función}.
Supongamos que queremos encontrar el valor más pequeño $k$
que sea una solución válida para un problema.
Se nos da una función $\texttt{ok}(x)$
que devuelve \texttt{true} si $x$ es una solución válida
y \texttt{false} de lo contrario.
Además, sabemos que $\texttt{ok}(x)$ es \texttt{false}
cuando $x<k$ y \texttt{true} cuando $x \ge k$.
La situación se ve de la siguiente manera:

\begin{center}
\begin{tabular}{r|rrrrrrrr}
$x$ & 0 & 1 & $\cdots$ & $k-1$ & $k$ & $k+1$ & $\cdots$ \\
\hline
$\texttt{ok}(x)$ & \texttt{false} & \texttt{false}
& $\cdots$ & \texttt{false} & \texttt{true} & \texttt{true} & $\cdots$ \\
\end{tabular}
\end{center}

\noindent
Ahora, el valor de $k$ se puede encontrar usando la búsqueda binaria:

\begin{lstlisting}
int x = -1;
for (int b = z; b >= 1; b /= 2) {
    while (!ok(x+b)) x += b;
}
int k = x+1;
\end{lstlisting}

La búsqueda encuentra el valor más grande de $x$ para el cual
$\texttt{ok}(x)$ es \texttt{false}.
Por lo tanto, el siguiente valor $k=x+1$
es el valor más pequeño posible para el cual
$\texttt{ok}(k)$ es \texttt{true}.
La longitud de salto inicial $z$ tiene que ser
lo suficientemente grande, por ejemplo, algún valor
para el que sabemos de antemano que $\texttt{ok}(z)$ es \texttt{true}.

El algoritmo llama a la función \texttt{ok}
$O(\log z)$ veces, por lo que la complejidad temporal total
depende de la función \texttt{ok}.
Por ejemplo, si la función funciona en tiempo $O(n)$,
la complejidad temporal total es $O(n \log z)$.

\subsubsection{Encontrar el valor máximo}

La búsqueda binaria también se puede utilizar para encontrar
el valor máximo de una función que es
primero creciente y luego decreciente.
Nuestra tarea es encontrar una posición $k$ tal que

\begin{itemize}
\item
$f(x)<f(x+1)$ cuando $x<k$, y
\item
$f(x)>f(x+1)$ cuando $x \ge k$.
\end{itemize}

La idea es usar la búsqueda binaria
para encontrar el valor más grande de $x$
para el cual $f(x)<f(x+1)$.
Esto implica que $k=x+1$
porque $f(x+1)>f(x+2)$.
El siguiente código implementa la búsqueda:

\begin{lstlisting}
int x = -1;
for (int b = z; b >= 1; b /= 2) {
    while (f(x+b) < f(x+b+1)) x += b;
}
int k = x+1;
\end{lstlisting}

Tenga en cuenta que a diferencia de la búsqueda binaria ordinaria,
aquí no se permite que los valores consecutivos
de la función sean iguales.
En este caso, no sería posible saber
cómo continuar la búsqueda.