Búsqueda binaria

Código en:JavaC#PythonJavaScript

En resumen: La búsqueda binaria encuentra un valor en un arreglo ordenado comparando con la mitad y descartando la otra mitad cada vez: O(log n) comparaciones.

Problema

El filtro que lee todo el catálogo

La tienda tiene 1 000 000 de productos, y la lista de precios está ordenada por precio. El filtro «precio exacto» busca con un bucle desde el principio, como la búsqueda lineal. Los precios en el código están en céntimos de euro: de 2 a 2 000 000. Un cliente busca un producto a 20.000,01 €, y no hay ninguno:

int n = 1_000_000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;

int comparisons = 0;
int found = -1;
for (int i = 0; i < n; i++)
{
    comparisons++;
    if (prices[i] == target)
    {
        found = i;
        break;
    }
}
Console.WriteLine("Índice: " + found);
Console.WriteLine("Comparaciones: " + comparisons);

Salida

Índice: -1
Comparaciones: 1000000

Un millón de comparaciones para decir «ninguno». Y cada vez que se abre la página, el filtro se ejecuta para decenas de precios.

Los precios están ordenados, y el bucle no lo aprovecha. Cuando buscas una palabra en un diccionario, no lees desde la primera página. Lo abres por la mitad y ves si la palabra va antes o después.

La idea

Pregunta por la mitad, descarta la otra mitad

Mira el precio de la mitad de la lista:

• si es el que buscas, terminaste;
• si es menor, el que buscas solo puede estar a la derecha. La mitad izquierda queda fuera, junto con la del medio;
• si es mayor, el que buscas solo puede estar a la izquierda.

Después, lo mismo con la mitad que queda. Esto es la búsqueda binaria. El rango donde el precio aún puede estar se guarda con dos índices: lo (el comienzo) y hi (el final). La mitad es mid.

Cada comparación reduce el rango a la mitad. 1 000 000 de precios pasan a 500 000, luego a 250 000, y tras unas 20 reducciones queda uno. Cuántas veces divides entre 2 hasta llegar a 1 se llama logaritmo en base 2: log₂ 1 000 000 ≈ 20. Por eso la búsqueda binaria es O(log n) y la lineal es O(n).

Hay una condición: el arreglo debe estar ordenado. En un arreglo sin ordenar, «es menor, así que está a la derecha» no es cierto.

Míralo

lo, mid y hi en la lista de precios

static int Find(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target)
        {
            return mid;
        }
        else if (prices[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
Console.WriteLine("Índice: " + Find(prices, 49));

Salida

Índice: 12

static int Find(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target)
        {
            return mid;
        }
        else if (prices[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

Paso a paso, en palabras

1. La lista de precios está ordenada: 15 precios. Buscamos 49 €. lo y hi abarcan todo, de 0 a 14.
2. mid = 7: 27 € < 49 €, así que el precio está a la derecha. lo = 8, la parte izquierda queda fuera. Quedan 7 precios.
3. mid = 11: 44 € < 49 €, así que el precio está a la derecha. lo = 12, la parte izquierda queda fuera. Quedan 3 precios.
4. mid = 13: 53 € > 49 €, así que el precio está a la izquierda. hi = 12, la parte derecha queda fuera. Queda 1 precio.
5. mid = 12: 49 €. Ese es el precio buscado: find devuelve 12.
6. 4 comparaciones. Una búsqueda desde el principio habría mirado 13 precios; con 1 000 000 de precios la búsqueda binaria necesita como máximo 20.

La mitad es lo + (hi - lo) / 2, no (lo + hi) / 2. Las dos dan el mismo número, pero la segunda puede desbordarse. Por qué, está en una de las siguientes tarjetas.

Más precisamente, para curiosos

El peor caso es que el precio no esté: el rango se divide a la mitad hasta que lo pasa a hi. Con n precios son como máximo ⌊log₂ n⌋ + 1 comparaciones: 4 para 10 precios, 10 para 1000, 20 para 1 000 000. El mejor caso es una comparación: el precio está justo en la mitad.

Aquí una «comparación» es una prueba de mid. La comprobación de igual y la de menor son dos líneas en el código, pero preguntan por el mismo precio.

Pruébalo

Predice cuántas pruebas

Precios ordenados en céntimos de euro: 2, 4, 6, …, 2000. Buscamos 2001, y no existe ese precio. ¿Cuántas veces se ejecuta el bucle?

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int target = 2 * n + 1;

int steps = 0;
int lo = 0;
int hi = n - 1;
while (lo <= hi)
{
    int mid = lo + (hi - lo) / 2;
    steps++;
    if (prices[mid] == target)
    {
        break;
    }
    else if (prices[mid] < target)
    {
        lo = mid + 1;
    }
    else
    {
        hi = mid - 1;
    }
}
Console.WriteLine(steps);

Respuesta

1000

500

10

Comprobar

Pruébalo

Completa

El precio en mid es menor que el que buscas. ¿Dónde empieza el nuevo rango?

static int Find(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target)
        {
            return mid;
        }
        else if (prices[mid] < target)
        {
            lo = ;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

Comprobar

La idea

Los límites: donde todos se equivocan

La búsqueda binaria se escribe en seis líneas y es famosa por escribirse mal. El error casi siempre es por uno: < en lugar de <=, mid en lugar de mid - 1. Se llama error off-by-one.

Te proteges con una decisión: qué significan lo y hi. Después te atienes a ella en todas partes.

• Rango cerrado [lo, hi]: ambos extremos pueden ser el precio. hi empieza en el último índice, el bucle se ejecuta mientras lo <= hi, y la mitad se descarta con hi = mid - 1 y lo = mid + 1. Ese es el find de arriba.
• Rango semiabierto [lo, hi): hi es el primer lugar después del rango. hi empieza en la longitud del arreglo, el bucle se ejecuta mientras lo < hi, y se va a la izquierda con hi = mid, porque hi no está en el rango de todos modos.

Los dos son correctos. El error es mezclarlos. Aquí hay un rango cerrado con hi = mid del semiabierto. Buscamos 4 €, y no existe ese precio. Un tope detiene el bucle tras 8 pruebas; de lo contrario no terminaría nunca:

static int Find(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length - 1;
    int probes = 0;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        Console.WriteLine($"lo={lo} hi={hi} mid={mid}");
        if (++probes == 8)
        {
            Console.WriteLine("Me detengo tras 8 intentos: lo y hi no se mueven");
            return -1;
        }
        if (prices[mid] == target)
        {
            return mid;
        }
        else if (prices[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid;
        }
    }
    return -1;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
Find(prices, 4);

Salida

lo=0 hi=14 mid=7
lo=0 hi=7 mid=3
lo=0 hi=3 mid=1
lo=0 hi=1 mid=0
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
lo=1 hi=1 mid=1
Me detengo tras 8 intentos: lo y hi no se mueven

Cuando lo y hi valen 1, la mitad es 1, el precio ahí es 5 €, más que 4 €, y hi = mid vuelve a ser 1. Nada cambia. Esto es un bucle infinito: el programa no falla, se queda colgado.

Pruébalo

Encuentra el error

La búsqueda encuentra 49 €, pero no encuentra el producto más caro, 58 €, aunque está en la lista de precios:

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36, 40, 44, 49, 53, 58];
Console.WriteLine("Índice: " + Find(prices, 58));

Salida

Índice: -1

Elige la línea con el error.

1static int Find(int[] prices, int target)2{3 int lo = 0;4 int hi = prices.Length - 1;5 while (lo < hi)6 {7 int mid = lo + (hi - lo) / 2;8 if (prices[mid] == target)9 {10 return mid;11 }12 else if (prices[mid] < target)13 {14 lo = mid + 1;15 }16 else17 {18 hi = mid - 1;19 }20 }21 return -1;22}

Comprobar

La idea

Cuando (lo + hi) / 2 se desborda

Un int en C# llega hasta 2 147 483 647. Un arreglo con más de mil millones de elementos es raro, pero existe: un índice de archivo, un registro, una base de datos en memoria. Entonces lo + hi puede pasar el límite:

int lo = 1_500_000_000;
int hi = 2_000_000_000;
Console.WriteLine((lo + hi) / 2);
Console.WriteLine(lo + (hi - lo) / 2);
Console.WriteLine((lo + hi) >>> 1);

Salida

-397483648
1750000000
1750000000

La suma es 3 500 000 000. No cabe en un int, y C# no da ningún error: la envuelve en un número negativo. La mitad pasa a ser -397 483 648, y el índice -397 483 648 lanza una excepción. lo + (hi - lo) / 2 calcula lo mismo sin sumar: la diferencia siempre cabe. (lo + hi) >>> 1 es la otra forma: >>> desplaza los bits a la derecha tratando el número como no negativo, y eso es dividir entre 2.

Más precisamente, para curiosos

El error no es inventado. La búsqueda binaria de la biblioteca estándar de Java, Arrays.binarySearch, tuvo (low + high) / 2 durante nueve años. Joshua Bloch lo describió en 2006 en el artículo «Nearly All Binary Searches and Mergesorts are Broken»: un programa con un arreglo de más de 2³⁰ elementos falla con ArrayIndexOutOfBoundsException. Hoy ahí dice (low + high) >>> 1.

C# tiene el operador >>> desde la versión 11. Array.BinarySearch en .NET calcula la mitad con lo + ((hi - lo) >> 1).

Míralo

El primer precio desde 20 €

El filtro «precio desde 20 €» no busca un precio exacto. Busca el primer lugar donde el precio es al menos 20 €: desde ahí están todos los productos que debe mostrar. Esto se llama límite inferior (lower bound). También es la primera aparición: si entre los precios hay tres productos a 15 €, el límite inferior de 15 es el primero de ellos.

find no lo da: se detiene en el primer 15 que pisa. El límite inferior usa un rango semiabierto, y el bucle no se detiene cuando son iguales, sigue yendo a la izquierda:

static int LowerBound(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid;
        }
    }
    return lo;
}

int[] prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49];
Console.WriteLine("Find: " + Find(prices, 15));
int first = LowerBound(prices, 15);
Console.WriteLine("El primer 15 €: índice " + first);
Console.WriteLine("Productos a 15 €: " + (LowerBound(prices, 16) - first));
int from20 = LowerBound(prices, 20);
Console.WriteLine($"El primer precio desde 20 €: {prices[from20]} €");

Salida

Find: 5
El primer 15 €: índice 4
Productos a 15 €: 3
El primer precio desde 20 €: 24 €

Si el precio es menor que el que buscas, él y todo lo anterior quedan fuera: lo = mid + 1. Si no, mid puede ser la respuesta, así que se queda en el rango: hi = mid. El bucle termina cuando lo y hi se juntan, y ahí está el primer lugar con un precio ≥ al buscado. Si no hay tal lugar, lo es la longitud del arreglo. Cuántos productos cuestan 15 € es la diferencia entre dos límites inferiores: el de 16 y el de 15.

C# tiene una búsqueda binaria lista: Array.BinarySearch para un arreglo y List<T>.BinarySearch para una lista ordenada. Cuando el precio no está, devuelve el complemento a nivel de bits del lugar donde entraría: ~i lo deshace:

int[] prices = [3, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44, 49];
Console.WriteLine(Array.BinarySearch(prices, 24));
int i = Array.BinarySearch(prices, 20);
Console.WriteLine(i);
Console.WriteLine(~i);
Console.WriteLine(Array.BinarySearch(prices, 15));

Salida

8
-9
8
5

Con duplicados, Array.BinarySearch devuelve uno de los iguales, sin prometer cuál: para 15 € da 5, mientras que el primero está en 4. Para el límite inferior escribes tu propio método, como LowerBound.

Míralo

Mídelo: lineal contra binaria

Búsqueda lineal y binaria en la misma lista de precios ordenada, cuando el precio no está. La búsqueda lineal compara todos los precios: n comparaciones. La binaria hace 20 comparaciones con 1 000 000 de precios:

• Búsqueda lineal (cada precio) O(n)
• Búsqueda binaria O(log n)

Algoritmo	n = 10	n = 1000	n = 100.000	n = 1.000.000
Búsqueda lineal (cada precio)	10	1000	100.000	1.000.000
Búsqueda binaria	4	10	17	20

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

static int Find(int[] prices, int target)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (prices[mid] == target)
        {
            return mid;
        }
        else if (prices[mid] < target)
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
    return -1;
}

La curva binaria casi está plana: con 100 veces más precios sube unas 7 comparaciones. Por eso la búsqueda binaria está en todas partes donde algo está ordenado: índices de bases de datos, git bisect, encontrar la versión en la que una prueba empezó a fallar.

Ejercicio

El filtro de precios: de 10 € a 30 €

Resuélvelo en tu editor.

De 10 € a 30 €. El filtro muestra cuántos productos cuestan de 10 € a 30 € inclusive. La lista de precios está ordenada: 3 €, 5, 8, 12, 15, 15, 15, 19, 24, 27, 31, 36, 40, 44 y 49. No recorras todo el arreglo: con dos búsquedas binarias encuentra el primer lugar con un precio ≥ 10 € y el primero con un precio ≥ 31 €. La diferencia es la cantidad.

Salida

De 10 € a 30 €: 7 productos

Más tareas

• La última aparición. Escribe UpperBound: el primer lugar con un precio mayor que el buscado. El último producto a 15 € está un lugar antes.
• Un hueco de entrega libre. Los huecos de entrega libres son un arreglo ordenado de minutos después de medianoche (540 son las 9:00). El cliente quiere la entrega no antes de las 14:10. Encuentra el primer hueco libre, o di que no hay.
• Dónde va el precio nuevo. Un producto nuevo a 21 € tiene que entrar en la lista de precios de modo que siga ordenada. Encuentra el lugar con búsqueda binaria.

Test

Ponte a prueba

1. La lista de precios tiene 1 000 000 de precios, ordenados de menor a mayor. ¿Cuántas comparaciones hace como máximo la búsqueda binaria?

100020500 000

2. El rango es cerrado: hi empieza en el último índice. ¿Qué condición del bucle es correcta?

lo <= hilo != hilo < hi

3. Con while (lo <= hi), alguien escribe hi = mid en lugar de hi = mid - 1. ¿Qué pasa?

Cuando lo y hi se juntan y el precio en mid es mayor, hi no cambia y el bucle nunca terminaEl programa no compilaNada, la búsqueda solo es un poco más lenta

4. Entre los precios hay tres productos a 15 €. ¿Qué lugar buscas para mostrar cada producto «desde 15 €»?

El 15 que encuentre la búsqueda binariaEl último 15 €El primer lugar con un precio ≥ 15 € (el límite inferior)

5. La lista de productos no está ordenada. ¿Puedes usar la búsqueda binaria?

Sí, solo es más lentaNo: la respuesta es incorrecta, porque la mitad que descartas puede contener el precioSí, si la lista es pequeña

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Complejidad en tiempo: contar pasos · Big-O: cómo crece el trabajo · Mejor caso, caso promedio y peor caso · Búsqueda lineal
• Continúa en: Búsqueda binaria sobre la respuesta · Exponenciación rápida · Divide y vencerás y el árbol de recursión · Árbol binario de búsqueda
• Ejercicios sobre el tema: Búsqueda