Capítulo 3: Algoritmos de Búsqueda y "Divide y Vencerás"

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {
        a += 1;
    }
}

Siguiendo los pasos anteriores, podemos entender:

• el tamaño del problema es n, ya que nuestro código va a depender de este.
• Tampoco hay casos peores o mejores, debido a que n es solo un valor entero y no podemos fijarnos en valores.
• La instrucción más significativa será j <= n, esta es la que más se repite en cualquier caso.
• Desarrollando la función del coste:

$$T(n)=T(n)*T(n)=T(n^2)$$

La complejidad temporal de este algoritmo es cuadrática.

A continuación estudiaremos otros algoritmos y analizaremos sus costes temporales.

Divide y Vencerás

Divide y Vencerás (o Divide and Conquer) es uno de los paradigmas de diseño de algoritmos más potentes y recurrentes en la programación competitiva. La idea fundamental se basa en la reducción de nuestro problema en problemas más pequeños, generalmente reduciendo el tamaño del input de manera recursiva, hasta que sean lo suficientemente simples como para ser resueltos directamente.

Cualquier algoritmo basado en Divide y Vencerás sigue siempre un patrón de tres pasos fundamentales:

1. Dividir: Romper el problema original en dos o más subproblemas más pequeños del mismo tipo. Generalmente, esto implica dividir el tamaño del input (N) a la mitad.
2. Vencer (Conquer): Resolver estos subproblemas de manera recursiva. Cuando el subproblema es lo suficientemente pequeño, llegamos a lo que se conoce como caso base, el cual se resuelve de manera directa y constante.
3. Combinar: Tomar las soluciones parciales de los subproblemas y unirlas para construir la solución correcta al problema original.

El impacto en la complejidad

Como vimos en la sección anterior sobre complejidad temporal, dividir el problema iterativamente es lo que nos permite alcanzar funciones de coste logarítmicas.

Piensa en cómo buscas una palabra en un diccionario físico. No empiezas por la página 1 y lees cada palabra hasta encontrarla (lo que sería una búsqueda lineal de coste $O(N)$). Lo que haces instintivamente es abrir el diccionario por la mitad. Si la palabra que buscas va antes alfabéticamente, descartas por completo la segunda mitad del diccionario y repites el proceso con la primera mitad.

Al descartar la mitad del problema en cada paso, el tamaño del input se reduce exponencialmente ($N, N/2, N/4, N/8...$). Esto es lo que nos otorga las complejidades de $O(\log N)$ en búsquedas, o $O(N \log N)$ en ordenaciones, permitiéndonos procesar arrays de $10^5$ elementos en milisegundos.

A lo largo del resto del capítulo, exploraremos cómo aplicar esta estrategia a algoritmos reales: desde encontrar valores ocultos (Búsquedas), pasando por organizar datos eficientemente (Ordenaciones), hasta realizar cálculos matemáticos con números gigantes (Exponenciación).

Algoritmos de búsqueda

Búsqueda binaria

Búsqueda binaria (o Binary Search) se basa en la búsqueda de un valor o solución de manera que se van descartando mitades del problema en los que se sabe que no se va a encontrar la solución. Para esto es vital tener cierto orden dentro del problema, debido a que si ese orden no existe, no se va a poder búsqueda binaria de ninguna forma.

Una de las aplicaciones más comunes es la búsqueda de un valor dentro de un array ordenado ascendentemente.

int bs(int arr[], int low, int high, int x)
{
if (high >= low) {
    int mid = low + (high - low) / 2;

    // Comprueba si el elemento es el del medio
    if (arr[mid] == x) return mid;

    // Si el elemento es menor que el del medio, 
    // sabemos que solo puede estar en la mitad inferior
    if (arr[mid] > x) return bs(arr, low, mid - 1, x);

    // En otro caso, está en la mitad superior
    return bs(arr, mid + 1, high, x);
}
return -1;  // No se encontró el número
}

// Método lanzadera
int bs(int arr[], int x) {
    return bs(arr, 0, arr.size() - 1, x);
}

En este ejemplo, vemos como la búsqueda dentro del array se va reduciendo a la mitad del tamaño con cada llamada que se realiza, haciendo que el máximo de llamadas que se requieren hacer sea, como máximo, (log n) llamadas. De esta forma, el coste temporal del algoritmo es bastante menor que en una búsqueda lineal en el peor caso:

$$T(n)\in \Omega(1),O(log\ n)$$

Búsqueda binaria en la respuesta (Binary Search on Answer)

Uno de los usos más potentes y frecuentes de la búsqueda binaria en programación competitiva no es buscar un elemento dentro de un array, sino buscar la respuesta final del problema dentro de un rango de valores posibles. A esta técnica se le conoce como binary search on answer.

En muchos problemas te pedirán maximizar o minimizar un valor bajo ciertas condiciones. Frases típicas como "encuentra el mínimo valor máximo posible" o "calcula el máximo tiempo mínimo" son señales de alarma casi garantizadas de que debes aplicar esta técnica.

La condición mágica: La función monótona

Para poder hacer búsqueda binaria sobre una respuesta, el problema debe cumplir una propiedad matemática estricta llamada monotonía. Esto significa que si creamos una función check(x) que nos diga si un valor $x$ cumple las condiciones del problema, sus respuestas deben dividirse en dos bloques continuos.

Por ejemplo, si buscamos el máximo valor posible que cumple una condición, la función check(x) debe devolver verdadero para valores pequeños y falso para valores grandes, formando un patrón así:
[True, True, True, True, False, False, False]

Nuestro objetivo con la búsqueda binaria ya no es buscar un número exacto, sino encontrar el punto de transición (el último True o el primer False).

Ejemplo práctico: Ascensores con nivel

En este problema, el objetivo es encontrar el nivel mínimo necesario que le permita a Kevin llegar desde la planta 0 hasta la planta más alta del edificio, utilizando una serie de ascensores que tienen restricciones de nivel.

Si analizamos el problema, descubrimos rápidamente el patrón monótono: si con un nivel cualquiera (por ejemplo, el nivel 10) es posible llegar a la azotea, entonces es obvio que con el nivel 11, 12 o 100 también podremos llegar. Por el contrario, si con el nivel 9 no llegamos, tampoco llegaremos con un nivel inferior.

Si evaluáramos todos los niveles posibles desde el 1 hasta el $10^6$, obtendríamos una secuencia de falsos (False) seguidos de verdaderos (True):
[False, False, False, False, True, True, True, True, True, ...]

La función check

Para aplicar la técnica, asumiremos que existe una función check(x). Esta función simplemente simulará el viaje y nos devolverá true si es posible llegar arriba usando solo ascensores de nivel $\le$ x, y false en caso contrario.

En este problema concreto, la función check se implementaría iterando los ascensores y uniendo sus intervalos de recorrido para ver si dejan algún "hueco" sin cubrir, pero a efectos de entender la búsqueda binaria, solo necesitamos saber que esta comprobación nos costará un tiempo de $O(N)$.

El esqueleto de la búsqueda binaria

Sabiendo que tenemos esa función que comprueba si una respuesta es válida, la implementación de la búsqueda binaria sobre la respuesta siempre sigue una estructura casi idéntica:

// Definimos nuestro espacio de búsqueda (según los límites del problema)
int low = 1;             // El nivel mínimo posible
int high = 1000000;      // El nivel máximo posible
int respuesta = high;    // Variable para guardar el mejor resultado encontrado

// Búsqueda binaria clásica
while (low <= high) {
    int mid = low + (high - low) / 2;
    
    // Usamos nuestra función 'check' para evaluar el valor intermedio
    if (check(mid)) {
        // Si el nivel 'mid' es suficiente, lo guardamos como posible respuesta
        respuesta = mid;
        
        // Como buscamos el nivel MÍNIMO, descartamos la mitad superior
        // e intentamos buscar en la mitad inferior
        high = mid - 1;
    } else {
        // Si no es suficiente, necesitamos obligatoriamente más nivel
        // Descartamos la mitad inferior
        low = mid + 1;
    }
}

// Al terminar el bucle, 'respuesta' contendrá el nivel mínimo exacto
cout << respuesta << "\n";

¿Por qué esto es tan potente? Aunque nuestra función check tenga que revisar los $N$ ascensores cada vez que se ejecuta, el bucle while cortará el espacio de búsqueda por la mitad en cada paso. Para $1.000.000$ de niveles posibles, el bucle solo se ejecutará unas $\log_2(1.000.000) \approx 20$ veces.

Búsqueda ternaria (Ternary search)

Ya hemos visto que la búsqueda binaria hace magia cuando tenemos una función monótona (que solo sube o solo baja, como un [F, F, T, T]). Pero, ¿qué pasa si la respuesta a nuestro problema forma una curva que primero baja y luego sube, como un valle? Aquí es donde podemos usar la Búsqueda ternaria.

La condición mágica: La función unimodal

La Búsqueda ternaria se utiliza para encontrar el punto máximo o mínimo de una función unimodal. Una función unimodal es aquella que tiene un único "pico" (crece estrictamente y luego decrece) o un único "valle" (decrece estrictamente y luego crece). Piensa en la forma de una letra "U" o una "U invertida" (una parábola).

Como la función cambia de dirección, la búsqueda binaria normal se vuelve loca, porque no sabe en qué lado de la curva está. Para solucionarlo, en lugar de dividir el espacio de búsqueda en 2 mitades con un punto central, lo dividimos en 3 tercios usando dos puntos intermedios ($m_1$ y $m_2$).

Supongamos que buscamos el mínimo (el fondo del valle). Si evaluamos nuestra función en $m_1$ y $m_2$, pueden pasar dos cosas principales:

• Si f(m1) > f(m2): Significa que la función está bajando hacia la derecha. El mínimo absoluto nunca estará en el tercio izquierdo (antes de $m_1$), así que lo descartamos entero.
• Si f(m1) < f(m2): Significa que la función ya está subiendo. El mínimo nunca estará en el tercio derecho (después de $m_2$), así que descartamos esa parte.

Ejemplo intuitivo: El precio perfecto para unas camisetas

Imagina que tu club de programación va a vender camisetas para financiarse y tienes que decidir el precio de venta exacto (entre 1€ y 100€) para maximizar los beneficios totales.

Por puro sentido común, sabes lo siguiente:

• Si el precio es muy bajo (ej. 2€): Todo el mundo querrá una camiseta, pero ganarás tan poco por cada una que el beneficio total será bajísimo.
• Si el precio es muy alto (ej. 90€): Ganarías muchísimo por cada venta, pero el problema es que casi nadie te la comprará, así que el beneficio total también será bajísimo o nulo.

En algún punto intermedio (por ejemplo, a 15€) se encuentra el equilibrio perfecto donde vendes suficientes camisetas a un buen margen. Si graficas el beneficio para cada precio de 1€ a 100€, verás que la línea sube hasta llegar al precio ideal, y luego empieza a bajar. Es una montaña perfecta.

La función beneficio(precio)

Asumiremos que tenemos una función mágica beneficio(precio) que nos calcula el dinero total que ganaríamos si ponemos ese precio. En lugar de probar los 100 precios uno por uno, usaremos Búsqueda Ternaria para escalar la montaña rápidamente.

Si tomamos dos precios de prueba, $m_1$ (ej. 33€) y $m_2$ (ej. 66€), pueden pasar dos cosas:

• Si beneficio(m1) < beneficio(m2): La montaña va subiendo hacia la derecha. Es imposible que el pico esté en el tercio izquierdo (antes de $m_1$), así que descartamos esa zona.
• Si beneficio(m1) > beneficio(m2): La montaña ya va de bajada. Es imposible que el pico esté en el tercio derecho (después de $m_2$), así que descartamos esa zona.

El esqueleto de la Búsqueda ternaria

// Definimos el espacio de búsqueda (precios posibles)
int low = 1;
int high = 100;

while (low <= high) {
    // Calculamos los dos puntos que dividen el rango en 3 tercios
    int m1 = low + (high - low) / 3;
    int m2 = high - (high - low) / 3;

    // Evaluamos nuestra función buscando el MÁXIMO
    if (beneficio(m1) < beneficio(m2)) {
        // La montaña sube hacia la derecha.
        // El pico máximo NO puede estar a la izquierda de m1.
        low = m1; 
    } else {
        // La montaña es más alta a la izquierda o va de bajada.
        // El pico máximo NO puede estar a la derecha de m2.
        high = m2; 
    }
}

Análisis de complejidad: Aunque parezca que descartar un tercio es más lento que descartar una mitad entera (como hace la Búsqueda Binaria), la complejidad sigue siendo logarítmica: $O(\log_3(\text{Rango}))$. Si en lugar de precios estuviéramos buscando entre mil millones de valores, el bucle solo necesitaría ejecutarse unas 40 veces para encontrar el pico exacto de la montaña.

Algoritmos de Ordenación

Las ordenaciones son algoritmos que permiten ordenar una secuencia de valores, ya sea de manera ascendente o descendente. Su utilidad viene de que podemos aprovechar que estas secuencias están ordenadas para aplicar ciertos algoritmos que son más óptimos que los convencionales para problemas que no están ordenados. A continuación veremos diferentes algoritmos de ordenación:

Función de utilidad

Los lenguajes de programación como Python, Java o C++ tienen funciones para ordenar listas fácilmente, en C++ se usa sort(). Estos son sus 3 usos principales:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3;

    // Ordenar arrays
    int a[n]; // [3, 1, 2]
    sort(a, a+n); // Ordenar n posiciones del array a empezando por el primer elemento

    // Ordenar strings...
    string s = "test";
    sort(s.begin(), s.end()); // Iteradores del principio y fin de la string

    // ... y vectores
    vector<int> v(n);  // [3, 1, 2]
    sort(v.begin(), v.end()); // Iteradores del principio y fin del vector
}

El uso de sort() es poco transparente, no se sabe a simple vista que pasa exactamente cuando llamamos a la función. Es la forma más eficiente de ordenar arrays y listas, por lo general no se deberían implementar funciones propias cada problema. Sin embargo este capítulo se explican algunos algoritmos de ordenación importantes que hay que saberse.

Merge sort

Basado en la técnica de Divide y Vencerás, el algoritmo de merge sort se divide en los siguientes pasos:

• Caso base: Cualquier lista de tamaño 1 está ordenada.
• Partiendo de lo anterior, se divide de manera recursiva la lista a ordenar hasta que todas las sublistas son de tamaño 1.
• A partir de ahora, combinar y ordenar pares de sublistas que se han obtenido de manera recursiva, hasta que se alcanza la lista completamente ordenada, sabiendo que es más eficiente ordenar dos listas ordenadas que dos listas no ordenadas.

Este ejemplo lo dejará más claro:

Inicio:                  [2, 13, 9, 7, 10, 32, 11]
Division 0:     [2, 13, 9, 7]                 [10, 32, 11]
División 1:   [2, 13]        [9, 7]        [10, 32]     [11]
División 3: [2]    [13]    [9]    [7]    [10]    [32]   [11]
Unión 0:       [2, 13]        [7, 9]        [10, 32]     [11]
Unión 1:        [2, 7, 9, 13]                 [10, 11, 32]
Unión 2:                  [2, 7, 9, 10, 11, 13, 32]

De esta forma, el merge sort consigue un coste temporal de:

$$T(n)=O(n log n)$$

Una posible implementación en C++ es:

void merge(vector<int> &res, vector<int> &l1, vector<int> &l2) {
    // Combina y ordena ambas listas en res
    int i1 = 0, i2 = 0;
    for (int i = 0; i < res.size(); i++) {
        if (l1.size() == i1) {
            res[i] = l2[i2++];
        } else if (l2.size() == i2) {
            res[i] = l1[i1++];
        } else if (l2[i2] < l1[i1]) {
            res[i] = l2[i2++];
        } else {
            res[i] = l1[i1++];
        }
    }
}


void solve(vector<int> &l) {
    // Caso base
    if (l.size() == 1) { return; }
    
    // División de la lista
    int mid = (l.size() / 2) - 1;
    vector<int> l1(l.begin(), l.begin() + mid + 1);
    vector<int> l2(l.begin() + mid + 1, l.begin() + l.size());
    
    // Llamada recursiva para dividir
    solve(l1);
    solve(l2);
    
    // Unir sublistas
    merge(l, l1, l2);
}

Quick sort

Al igual que el Merge sort, el algoritmo Quick sort también se basa en la técnica de Divide y Vencerás. Este tipo de algoritmos consiste en partir el problema en partes más pequeñas hasta que cada parte sea lo suficientemente simple para que se pueda resolver de manera directa.

Hay multiples formas de implementar Quick sort, cada una tiene sus diferencias aunque la idea principal es la misma. Vamos a ver como se puede implementar de la forma más eficiente en cuanto a memoria, 'in-place', que significa que no usaremos ningún array auxiliar:

Comenzamos con una lista de elementos sin ordenar:

[1, 5, 9, 4, 2, 3, 3, 8, 5]

Ahora, repetiremos los pasos a continuación hasta que toda la lista este ordenada. Aunque primero debemos que comprender el concepto pivote, es un elemento que seleccionaremos al azar en el segmento de la lista que queremos ordenar. Cuando hayamos elegido pivote, tendremos que mover los elementos menores a este a un lado del pivote y los que son mayores al otro lado; de esta manera sabemos que el pivote está ordenado, en su posición final, y ahora tendremos que aplicar Quick sort a ambos lados recursivamente para ordenar toda la lista.

1. Para el segmento que queremos ordenar, seleccionaremos un pivote, por ejemplo el último elemento del segmento.

2. Recorremos todos los elementos del segmento (menos el último) de principio a final

• Si un elemento es estrictamente más pequeño que el pivote, intercambiaremos este elemento por el primer elemento que no sea más pequeño que el pivote de la lista, para ello habrá que mantener un index que se incremente cada vez que realicemos un cambio. Por ejemplo para la lista inicial seleccionaremos el último elemento, 5, como pivote:

Iteración 0:
i = 0:  [1, 5, 9, 4, 2, 3, 3, 8, 5] // Se cambia 1 a la pos 0
i = 1:  [1, 5, 9, 4, 2, 3, 3, 8, 5] // No hace falta mover el 5
i = 2:  [1, 5, 9, 4, 2, 3, 3, 8, 5] // El 9 es mayor, no se mueve
i = 3:  [1, 4, 9, 5, 2, 3, 3, 8, 5] // Se cambia 4 a la pos 1
i = 4:  [1, 4, 2, 5, 9, 3, 3, 8, 5] // Se cambia 2 a la pos 2
i = 5:  [1, 4, 2, 3, 9, 5, 3, 8, 5] // Se cambia 3 a la pos 3
i = 6:  [1, 4, 2, 3, 3, 5, 9, 8, 5] // Se cambia 3 a la pos 4
i = 7:  [1, 4, 2, 3, 3, 5, 9, 8, 5] // El 8 es mayor, no se mueve
i = 8:  [1, 4, 2, 3, 3, 5, 9, 8, 5] // Se cambia el pivote a pos 5.

Y ahora tenemos los elementos más pequeños que el pivote a un lado y los más grandes a otros.

1. Ahora simplemente repetiremos desde el paso 1 para cada lado del segmento, sin incluir el pivote, ya que está ordenado.

Pese a que el algoritmo de Quick sort es muy potente, debemos tener en cuenta su mayor debilidad, y es que la elección del pivote es muy importante, dado que puede determinar si el algoritmo será eficiente. Para más información sobre la elección de pivotes, click aquí.

Dependiendo de la posición en la que acaba el pivote tras cada iteración, nos podemos encontrar frente a un best case si este termina en el medio, o un worst case, si el pivote acaba en un extremo de la lista, debido a que esto determinará la cantidad de llamadas recursivas que se deben hacer. Esto nos deja con una complejidad temporal de:

$$T(n) \in \Omega(n log n), O(n^2)$$

Una posible implementación es:

int *a;

void quicksort(int l, int r) { // Ambos índices válidos
    if (r-l < 1) return;
    int pivot = a[r]; // En este caso, cojemos el último
    int i = l, j = l;
    
    while (j <= r) {
        // Reemplazamos si es menor que el pivot
        if (a[j] < pivot) {
            swap(a[i], a[j]);
            ++i;
        }
        ++j;
    }
    
    // Cambia el pivot por su posición ordenada
    swap(a[i], a[r]);
    
    // Ordena ambos lados
    quicksort(l, i-1);
    quicksort(i+1, j-1);

}

Aplicaciones

Exponenciación binaria (Binary Exponentiation)

Hasta ahora hemos visto cómo aplicar la técnica de Divide y Vencerás para buscar elementos o respuestas. Sin embargo, este paradigma también es fundamental para optimizar algoritmos puramente matemáticos. El ejemplo más clásico en programación competitiva es la Exponenciación Binaria.

Imagina que necesitas calcular $a^b$ (por ejemplo, $3^{15}$). El enfoque tradicional sería hacer un bucle y multiplicar $a$ por sí mismo $b$ veces. Esto tiene un coste temporal de $O(b)$. Si el exponente $b$ es un número gigantesco, el bucle tardaría muchísimo en terminar y obtendrías un claro Time Limit Exceeded.

La matemática del Divide y Vencerás

La Exponenciación Binaria reduce el tiempo de ejecución a $O(\log b)$ aprovechando una propiedad matemática básica: podemos calcular una potencia dividiendo el exponente a la mitad en lugar de restarle uno.

• Si $b$ es par: $a^b = (a^{b/2})^2$
  (Ejemplo: $3^{10} = (3^5)^2$. Solo necesitamos calcular $3^5$ una vez y multiplicarlo por sí mismo).
• Si $b$ es impar: $a^b = a \cdot a^{b-1}$
  (Ejemplo: $3^{11} = 3 \cdot 3^{10}$. Al restar 1, el exponente se vuelve par y podemos aplicar la regla anterior).
• Caso base: $a^0 = 1$.

Implementación Recursiva

La versión recursiva es la traducción literal a código de la explicación matemática que acabamos de ver. Es muy fácil de entender y de implementar.

#include <bits/stdc++.h>
using namespace std;

long long binpow_recursivo(long long a, long long b) {
    // Caso base: cualquier número elevado a 0 es 1
    if (b == 0) return 1;
    
    // Divide y Vencerás: calculamos la mitad del problema
    long long mitad = binpow_recursivo(a, b / 2);
    
    // Combinamos elevando la mitad al cuadrado
    long long res = mitad * mitad;
    
    // Si el exponente original era impar, multiplicamos por 'a' una vez más
    if (b % 2 != 0) {
        res = res * a;
    }
    
    return res;
}

Implementación Iterativa

Aunque la versión recursiva es de coste $O(\log b)$, las llamadas recursivas consumen memoria en la pila (stack) y un poco de tiempo extra. Por ello, es muy común utilizar la versión iterativa.

Esta versión funciona analizando la representación en binario del exponente $b$. Mientras dividimos el exponente por 2 en cada paso (b >>= 1), vamos elevando nuestra base al cuadrado consecutivamente ($a^1, a^2, a^4, a^8 \dots$). Si el bit actual de $b$ es 1 (el número es impar, b & 1), multiplicamos ese cuadrado actual a nuestro resultado final.

#include <bits/stdc++.h>
using namespace std;

long long binpow_iterativo(long long a, long long b) {
    long long res = 1;  // Aquí iremos acumulando la respuesta
    
    while (b > 0) {
        // Si el exponente es impar (su bit menos significativo es 1)
        if (b & 1) {
            res = res * a;
        }
        
        // Elevamos la base al cuadrado para el siguiente bit
        a = a * a;
        
        // Dividimos el exponente a la mitad (desplazamiento de bits a la derecha)
        b >>= 1;
    }
    
    return res;
}

¿Por qué es tan rápido? Si el exponente es $b = 10^{18}$, el bucle while iterativo (o la profundidad de la recursividad) solo se ejecutará unas $\log_2(10^{18}) \approx 60$ veces. ¡Hemos transformado una operación que llevaría billones de pasos en un cálculo que se resuelve en unos pocos saltos!