Búsqueda binaria: lower bound, arreglo rotado y búsqueda por respuesta

1. Descripción general

La búsqueda binaria es un algoritmo de búsqueda sobre datos ya ordenados con complejidad O(log n). La idea es muy simple, pero la implementación es propensa a errores: bucle infinito, error de un elemento (off-by-one), desbordamiento al calcular mid.

Este artículo va desde la versión básica hasta las variantes comunes: encontrar la posición de inicio/fin de elementos duplicados, contar ocurrencias, buscar en un arreglo rotado, y búsqueda binaria por respuesta. Al terminar, tendrás un conjunto de plantillas de implementación confiables, acompañadas de pruebas para verificarlas.

2. Búsqueda binaria básica

Supongamos que tienes un arreglo de precios de productos ordenados en orden ascendente y necesitas encontrar la posición de un precio específico:

public final class PriceSearch {

    public static int search(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;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

Explicación:

• lo y hi forman un intervalo cerrado [lo, hi]. Esta es la región donde target puede estar.
• La condición lo <= hi significa que el bucle continúa mientras el intervalo contiene al menos un elemento.
• mid = lo + (hi - lo) / 2 evita desbordamiento. La forma (lo + hi) / 2 se desbordaría cuando lo + hi excede Integer.MAX_VALUE. Una forma equivalente es (lo + hi) >>> 1.
• Después de cada paso, excluimos mid del intervalo (con mid + 1 o mid - 1), así que el intervalo siempre se reduce y el bucle termina con seguridad.

Resultado:

3
-1

Esta versión es suficiente cuando el arreglo no tiene elementos duplicados y solo necesitas saber “existe o no”. Cuando hay elementos duplicados, devuelve cualquier posición dentro del grupo de duplicados. Generalmente no es lo que quieres.

3. Lower bound y upper bound

Las dos variantes más importantes son:

• lower bound: el primer índice donde a[i] >= target.
• upper bound: el primer índice donde a[i] > target.

Ambos siempre devuelven un índice en [0, n], incluso cuando target no está en el arreglo. Este índice es exactamente la posición de inserción para mantener el arreglo ordenado.

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // intervalo semiabierto [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Diferencias con respecto a la versión básica:

• Usamos un intervalo semiabierto [lo, hi), así que hi se inicializa con a.length y la condición del bucle es lo < hi.
• Cuando a[mid] satisface la condición “ya es lo suficientemente grande”, asignamos hi = mid en lugar de mid - 1, porque mid aún podría ser la respuesta.
• Las dos funciones difieren solo en los operadores < y <=.

Prueba con un arreglo que tiene elementos duplicados:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

Con 300, el resultado 4 indica que si insertamos 300, estaría antes de 350. Con 900, el resultado es n, lo que significa que todos los elementos son menores.

3.1. Posición de inicio, posición final y número de ocurrencias

A partir de estas dos funciones, puedes deducir inmediatamente los problemas comunes:

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

Con prices anterior y target = 200, obtenemos firstIndexOf = 1, lastIndexOf = 3, count = 3. Punto importante: siempre verifica los límites i < a.length (o i >= 0) antes de leer a[i].

3.2. Contar elementos en un rango

Una aplicación práctica es contar el número de pedidos con valor en [min, max]:

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

Con {100, 200, 200, 200, 350, 500} y rango [150, 400], el resultado es 6 - ... ? Calcula: upperBound(400) = 5, lowerBound(150) = 1, así que el resultado es 4. Cada consulta solo toma O(log n), sin necesidad de recorrer todo el arreglo.

4. Búsqueda en un arreglo rotado

Un arreglo rotado es un arreglo ya ordenado que ha sido “cortado” en un punto y sus dos mitades intercambiadas, por ejemplo {40, 50, 60, 10, 20, 30}. Este arreglo ya no está completamente ordenado, pero al menos una mitad alrededor de mid sigue siendo ordenada. Nos basamos en esto para decidir hacia dónde ir:

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // mitad izquierda está ordenada
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // mitad derecha está ordenada
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

Explicación:

• a[lo] <= a[mid] indica que el intervalo [lo, mid] está ordenado. Si target cae dentro del rango de valores de este intervalo, nos enfocamos en la izquierda. De lo contrario, nos enfocamos en la derecha.
• En el otro caso, el intervalo [mid, hi] está ordenado, y razonamos de forma análoga.

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

Nota: Esta implementación asume que el arreglo no tiene elementos duplicados. Con un arreglo como {2, 2, 2, 3, 2}, la condición a[lo] <= a[mid] no puede distinguir cuál mitad está ordenada. En ese caso, debes manejar el caso especial a[lo] == a[mid] incrementando lo en uno, y la complejidad en el peor caso se convierte en O(n).

5. Búsqueda binaria por respuesta

Esta es la variante más poderosa. No busca en un arreglo sino que busca el valor mínimo que satisface una condición. El único requisito para aplicarla es que el predicado debe ser monótono: si x lo satisface, entonces todo valor mayor que x también lo satisface. En otras palabras, la secuencia de resultados tiene la forma false, false, ..., true, true.

Escribimos una función general:

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** El valor mínimo en [lo, hi] donde ok devuelve true. Se asume que ok(hi) == true. */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Esta función tiene la misma estructura que lowerBound. De hecho, lowerBound es solo un caso especial con predicado a[i] >= target.

Aplicación a un problema real: un almacén tiene una lista de paquetes en un orden fijo, necesita entregarlos en maxDays días. Cada día el vehículo lleva paquetes consecutivos, con el peso total no excediendo la capacidad del vehículo. ¿Cuál es la capacidad mínima necesaria?

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

Explicación:

• lo es el paquete más pesado, porque el vehículo debe poder llevar al menos un paquete cualquiera. hi es el peso total, porque entonces solo se necesita un día. Por lo tanto, ok(hi) es definitivamente verdadero.
• canShip simula un enfoque codicioso: carga paquetes en el vehículo hasta que se sobrecarga, luego cambia a un nuevo día. Cuanto mayor sea la capacidad, menos días se necesitan, así que el predicado es monótono.
• El costo total es O(n · log(sum)), en lugar de probar cada capacidad.

6

Con capacidad 6, el horario de entrega es [3, 2], [2, 4], [1, 4], exactamente 3 días. Con capacidad 5, necesitamos 4 días, así que 5 no es suficiente.

Con este patrón se pueden resolver muchos otros problemas: número mínimo de threads para procesar batch a tiempo, límite de rate mínimo, raíz cuadrada entera de un número.

6. Usar la biblioteca estándar de Java

Java ya tiene Arrays.binarySearch y Collections.binarySearch. Necesitas comprender claramente los valores de retorno:

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• Si se encuentra, la función devuelve el índice del elemento.
• Si no se encuentra, la función devuelve -(insertionPoint) - 1. Aquí la posición de inserción es 4, así que el resultado es -5. Para obtener la posición de inserción nuevamente, calcula -(result) - 1.
• Cuando hay elementos duplicados, la documentación no garantiza qué posición dentro del grupo se devuelve. Si necesitas la primera o última posición, usa lowerBound/upperBound que escribiste tú mismo.

Para listas de objetos, pasas un Comparator que coincida con el orden ya ordenado:

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

Nota: Collections.binarySearch en LinkedList no alcanza O(log n) porque acceder por índice cuesta O(n). Usa ArrayList o un arreglo.

7. Pruebas

Agrega las dependencias de JUnit 5 y AssertJ. Si tu proyecto usa spring-boot-starter-test, ambas ya están incluidas.

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

Escribe pruebas para casos límite. Este es el lugar donde la búsqueda binaria tiende a fallar más:

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

La prueba lowerBoundMatchesLinearScan compara con el conteo lineal en 1.000 arreglos aleatorios, incluyendo arreglos vacíos. Este tipo de prueba de comparación atrapa errores off-by-one mucho mejor que unos pocos ejemplos escritos a mano.

8. Errores comunes y cuándo no usar búsqueda binaria

Errores comunes:

• Mezclar dos convenciones de intervalo. Inicializas hi = n (semiabierto) pero luego haces while (lo <= hi) y asignas hi = mid - 1. Esto resulta en lectura fuera del arreglo. Elige una convención y mantenla consistente.
• Bucle infinito. Si escribes lo = mid junto con mid = (lo + hi) / 2, cuando hi = lo + 1 entonces mid == lo y el intervalo no se reduce. Si realmente necesitas lo = mid, redondea hacia arriba: mid = lo + (hi - lo + 1) / 2.
• Desbordamiento al calcular mid o al calcular la suma en búsqueda binaria por respuesta. Usa long para valores que podrían ser grandes.
• Predicado no monótono. La búsqueda binaria aún devuelve un número, pero ese número es sin sentido. Demuestra la monotonía antes de aplicarla.

Cuándo no usar búsqueda binaria:

• Los datos no están ordenados y solo buscas algunas veces. Ordenar cuesta O(n log n), mientras que buscar linealmente cuesta O(n).
• Solo necesitas verificar “existe o no” con muchas búsquedas. En ese caso, HashSet proporciona O(1) promedio.
• Los datos cambian continuamente y necesitas insertar y eliminar frecuentemente. Mantener el arreglo ordenado cuesta O(n) por inserción. Considera TreeMap/TreeSet, que ya tienen ceilingKey, floorKey, higherKey equivalentes a lower bound y upper bound.
• El arreglo es muy pequeño, solo decenas de elementos. El recorrido lineal generalmente es tan rápido o más rápido gracias al cache, y el código es más simple.

9. Conclusión

La búsqueda binaria no es solo “encontrar un elemento en un arreglo”. Una vez que domines lower bound y upper bound con el intervalo semiabierto [lo, hi), puedes resolver problemas de posición de inicio/fin, conteo de elementos y conteo por rango con solo unas líneas. Un arreglo rotado requiere un paso adicional para identificar cuál mitad está ordenada. La búsqueda binaria por respuesta extiende la técnica a cualquier problema con predicado monótono.

Mantén una única convención de intervalo, usa >>> o lo + (hi - lo) / 2 para evitar desbordamiento, y siempre compara con búsqueda lineal en tus pruebas. Estos tres hábitos eliminan casi todos los errores por los que la búsqueda binaria es famosa de cometer.