Búsqueda binaria sobre la respuesta

Qué cubre este capítulo

La búsqueda binaria, del bloque de búsqueda, encontraba un valor dentro de un array ordenado partiendo a la mitad el intervalo de búsqueda. Este capítulo aplica ese mismo partir a la mitad a algo que ni siquiera es un array: el espacio de posibles respuestas de un problema de optimización. Muchos problemas del tipo "encuentra el valor más chico (o más grande) tal que se cumpla cierta condición" no tienen una estructura de búsqueda visible, pero esconden una monótona: si un candidato a respuesta funciona, todos los candidatos mayores funcionan también (o todos los menores), así que las respuestas están implícitamente ordenadas por factibilidad — una racha de "no", un umbral, y luego una racha de "sí". Eso es justo lo que la búsqueda binaria necesita. El truco está en convertir la pregunta difícil de optimización ("¿cuál es el mínimo?") en una pregunta fácil de decisión ("¿este valor en particular funciona?"), y hacerle búsqueda binaria a la decisión. Aquí lo construimos sobre el problema de la partición del pintor — dividir un array en k partes minimizando la suma de la parte más grande — y verás cómo hace 20 verificaciones de factibilidad donde recorrer todos los candidatos haría 228,000.

Un poco de historia

La búsqueda binaria en sí es antiquísima en espíritu y se formalizó para computadoras en los años cuarenta y cincuenta (su primera implementación publicada libre de bugs, como notó Knuth, llegó sorprendentemente tarde — las condiciones de frontera son famosamente traicioneras). La "búsqueda binaria sobre la respuesta" no es tanto un descubrimiento aparte como un reconocimiento: darse cuenta de que el único requisito real de la búsqueda binaria es un predicado monótono, no un array ordenado físico. La misma idea aparece en análisis numérico como el método de bisección para encontrar raíces de funciones continuas (si f es continua y cambia de signo dentro de un intervalo, hazle búsqueda binaria al intervalo para hallar el cero), que viene del siglo XIX o antes. En diseño de algoritmos y programación competitiva se volvió un patrón con nombre propio y enseñado en los 2000, apreciado porque convierte toda una clase de problemas de optimización intimidantes en una decisión trivial más un ciclo. Su lección de fondo — que "optimizar" con frecuencia se reduce a "decidir, repetidamente" — hace eco de un tema central de la teoría de la complejidad, donde la relación entre problemas de optimización y de decisión es fundamental (un problema de optimización NP y su versión de decisión sí/no son polinomialmente equivalentes).

La intuición

Toma el problema: divide un array como [7, 2, 5, 10, 8] en k = 2 partes contiguas de modo que la suma de la parte más grande sea lo más chica posible. Optimizar esto directo es incómodo: ¿dónde van los puntos de corte? Pero conviértelo en una decisión: "¿podemos dividirlo en a lo más 2 partes, cada una sumando a lo más L?". Esa pregunta se responde fácil de forma greedy: recorre el array acumulando una suma corriente y, cuando agregar el siguiente elemento se pasaría de L, arranca una parte nueva; cuenta las partes y checa si son ≤ k. Y aquí viene la propiedad clave: esta decisión es monótona en L. Si un límite L funciona, cualquier límite mayor funciona también (más espacio por parte significa que no hacen falta más partes); si L es demasiado chico, todo lo que esté por debajo también lo es. Así que conforme L crece de chico a grande, la respuesta a "¿L funciona?" va falso, falso, …, falso, verdadero, verdadero, … — un solo umbral. El L más chico que funciona es exactamente la suma minimizada de la parte más grande que andamos buscando.

Ese umbral es lo que encuentra la búsqueda binaria. La respuesta tiene que estar entre max(nums) — ninguna parte puede ser menor que el elemento individual más grande — y sum(nums) — una sola parte que se lleva todo. Hazle búsqueda binaria a ese rango: prueba el punto medio L con la verificación greedy; si funciona, la respuesta es L o menor, así que baja la cota superior a L; si no funciona, la respuesta es mayor, así que sube la cota inferior por encima de L. Cada verificación es O(n) y solo hay O(log(rango)) de ellas, así que todo el asunto es O(n log(sum)) — un puñado de decisiones baratas en lugar de probar todos los L posibles. El patrón se generaliza a cualquier problema que puedas plantear como "la X más chica/más grande con una propiedad sí/no monótona", y reconocer esa forma — que una optimización es en secreto una búsqueda de umbral — es toda la habilidad.

Complejidad: cómo escala

La búsqueda binaria sobre la respuesta cuesta O(log(rango) × costo-de-una-verificación). Para el problema de la división, el rango es sum(nums) − max(nums) y cada verificación greedy es O(n), lo que da O(n log(sum)). Compara las alternativas: recorrer cada límite candidato es O(rango × n) — potencialmente enorme — y la programación dinámica exacta es O(n² k). El enfrentamiento mide el número de verificaciones de factibilidad contra un recorrido lineal del espacio de candidatos, conforme crece el rango de la respuesta:

La línea del recorrido lineal sube al parejo del rango de la respuesta — hay que checar cada candidato — mientras que la línea de la búsqueda binaria es casi plana, creciendo como su logaritmo. Cuando el espacio de respuestas abarca unos dos millones de valores, el recorrido lineal hace alrededor de 228,000 verificaciones de factibilidad; la búsqueda binaria hace 20 — once mil veces menos, y la razón sigue creciendo porque un lado es lineal en el rango y el otro logarítmico. Esta es la ganancia característica de la búsqueda binaria, ahora aplicada a respuestas en vez de a elementos de un array: cada verificación parte a la mitad las posibilidades restantes, así que duplicar el espacio de respuestas agrega apenas una verificación más. El valor de la técnica es que vuelve el tamaño del espacio de respuestas casi irrelevante — un rango de mil millones cuesta apenas ~30 verificaciones — y por eso es la herramienta para problemas donde la respuesta puede ser cualquier valor dentro de un rango numérico gigantesco.

En qué es buena y en qué no

La búsqueda binaria sobre la respuesta es la herramienta correcta para problemas de optimización de la forma "minimiza/maximiza X sujeto a una condición de factibilidad monótona", sobre todo cuando X recorre un espacio numérico grande. Los clásicos: problemas de "minimizar el máximo" y "maximizar el mínimo" (dividir un array, la partición del pintor o la asignación de libros, colocar k routers para minimizar el hueco más grande), planeación de capacidad y tasa (la capacidad de barco más chica para entregar en D días, la velocidad mínima de comida para terminar en H horas, el número mínimo de servidores para aguantar la carga), fechas límite de calendarización, y búsqueda numérica de raíces y solución de ecuaciones (el método de bisección). Se lleva de maravilla con una verificación de factibilidad greedy o de simulación — la pregunta de decisión suele ser muchísimo más fácil que la de optimización — y convierte problemas que parecen necesitar DP pesada o búsqueda exhaustiva en un ciclo cortito.

Donde no aplica es cuando el predicado de factibilidad no es monótono: si alguna X mayor falla donde una X menor tuvo éxito, el espacio de respuestas no está ordenado y la búsqueda binaria converge en una babosada; tienes que verificar la monotonía primero. También sale sobrando cuando el espacio de respuestas es diminuto (mejor recórrelo) o cuando una fórmula directa o un greedy te dan la respuesta de una. Y la verificación de factibilidad tiene que ser eficiente: si decidir "¿funciona X?" ya de por sí es caro, hacer O(log rango) de ellas puede no salir a cuenta. Por último, encuentra un valor umbral, no necesariamente la estructura completa de la solución (cuáles puntos de corte, cuál asignación) — muchas veces necesitas una segunda pasada para reconstruir la partición real una vez que conoces el límite óptimo. Su nicho es preciso: un predicado monótono sobre un espacio de respuestas grande pero recorrible, con un procedimiento de decisión barato.

Los datos, o las entradas

El enfrentamiento cuenta verificaciones de factibilidad para el problema de dividir el array — búsqueda binaria contra un recorrido lineal de todos los límites candidatos — conforme el rango de la respuesta se va a los millones. La correctitud se verifica sobre mil arrays aleatorios: la respuesta de la búsqueda binaria debe coincidir tanto con la programación dinámica exacta O(n²k) como con el recorrido lineal, se verifica que el predicado de factibilidad sea genuinamente monótono (una vez verdadero conforme crece el límite, nunca vuelve a ser falso), y el ejemplo de la raíz cuadrada entera se contrasta contra math.isqrt de Python sobre miles de números grandes. La animación le hace búsqueda binaria al espacio de respuestas [10, 32] para dividir [7, 2, 5, 10, 8] en 2 partes, probando la factibilidad de cada punto medio y estrechándose hasta el umbral.

Constrúyelo, una función a la vez

La verificación de factibilidad — la pregunta de decisión monótona fácil, respondida de forma greedy:

def can_split(nums, k, limit):
    """The DECISION question: can `nums` be cut into at most k contiguous parts, each with sum ≤
    limit? Greedily extend the current part until adding the next element would exceed `limit`, then
    start a new part. Count the parts. O(n). This is monotone in `limit`: a larger limit can only
    make splitting EASIER (fewer parts needed), which is exactly what lets us binary-search on it."""
    parts, current = 1, 0
    for x in nums:
        if x > limit:
            return False                          # one element alone exceeds the limit — impossible
        if current + x > limit:
            parts += 1                            # close this part, start a new one with x
            current = x
        else:
            current += x
    return parts <= k

Búsqueda binaria sobre el espacio de respuestas para hallar el límite factible más chico:

def min_largest_sum(nums, k):
    """Minimize the largest part-sum when splitting `nums` into k contiguous parts, by binary
    searching the ANSWER. The answer lies between max(nums) (no part can be smaller than the biggest
    single element) and sum(nums) (one part holds everything). Binary-search that range for the
    smallest limit the greedy check accepts. O(n · log(sum)) — a handful of O(n) checks, not a scan
    of every candidate. Returns the minimized largest-part sum."""
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(nums, k, mid):
            hi = mid                              # feasible → try to do even better (smaller)
        else:
            lo = mid + 1                          # infeasible → need a bigger limit
    return lo                                     # lo == hi == the smallest feasible limit

La misma idea en miniatura — la raíz cuadrada entera como búsqueda con predicado monótono:

def integer_sqrt(x):
    """A second, tiny example of the same idea: the integer square root of x is the largest v with
    v*v ≤ x — a monotone predicate (v*v ≤ x is true up to a threshold, false after), so binary-
    search v in [0, x]. O(log x), no floating point, exact."""
    lo, hi, ans = 0, x, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid                             # feasible → record it, look for a larger v
            lo = mid + 1
        else:
            hi = mid - 1                          # too big → look smaller
    return ans

Míralo trabajar

Aquí está la búsqueda binaria sobre el espacio de respuestas para dividir [7, 2, 5, 10, 8] en 2 partes minimizando la parte más grande. Las celdas son límites candidatos desde 10 (el elemento individual más grande — ninguna parte puede ser menor) hasta 32 (el total — una sola parte se lleva todo). A diferencia de la búsqueda binaria común, no hay datos en estas celdas contra los cuales comparar; en vez de eso, a cada punto medio que se prueba se le hace una pregunta: "¿podemos dividir en ≤ 2 partes, cada una sumando a lo más este límite?". Una celda verde significa sí (factible), roja significa no. Fíjate cómo se estrecha la búsqueda: prueba el medio y, como la factibilidad es monótona — todo límite arriba de la respuesta es verde, todo el que está abajo es rojo — un sí mueve la búsqueda a la izquierda (prueba algo más chico) y un no la mueve a la derecha (necesitas algo más grande). En un puñado de verificaciones de factibilidad converge en 18: el límite más chico que admite una división en 2 ([7,2,5] suma 14, [10,8] suma 18). Ninguna parte pasa de 18, y no hay límite menor posible:

El código completo

La pestaña "desde cero" trae la verificación de factibilidad, la búsqueda binaria sobre la respuesta y el ejemplo de la raíz cuadrada entera; la pestaña de librería trae la programación dinámica exacta O(n²k) (la referencia de correctitud) y el recorrido lineal (el contraste O(rango)). Cámbiate entre ellas: la búsqueda binaria y el recorrido lineal usan el predicado de factibilidad idéntico, y la única diferencia es que una parte a la mitad el espacio de búsqueda en cada paso y la otra lo recorre de uno en uno.

"""Binary search on the answer — apply binary search not to a sorted array of data, but to the
space of possible ANSWERS to an optimization problem. Many "find the minimum/maximum value such
that..." problems have no obvious search structure, yet hide one: if a candidate answer works,
every larger (or smaller) candidate works too. That MONOTONICITY means the space of answers is
sorted by feasibility — infeasible values, then a threshold, then feasible values — and you can
binary-search for the threshold, even though there's no array to look at.

The trick is to turn the optimization ("find the smallest X such that P holds") into a sequence of
DECISION questions ("does P hold for this specific X?"). Each decision is usually easy — a greedy
check or a simulation. Binary search asks O(log(range)) of them instead of trying every candidate.
The example: split an array into k contiguous parts to MINIMIZE the largest part's sum (the
"painter's partition" / load-balancing problem). Directly optimizing is awkward; but "can we split
into ≤ k parts each summing at most L?" is a trivial greedy check, and it's monotone in L — so we
binary-search L for the smallest feasible value.
"""


# region: feasible
def can_split(nums, k, limit):
    """The DECISION question: can `nums` be cut into at most k contiguous parts, each with sum ≤
    limit? Greedily extend the current part until adding the next element would exceed `limit`, then
    start a new part. Count the parts. O(n). This is monotone in `limit`: a larger limit can only
    make splitting EASIER (fewer parts needed), which is exactly what lets us binary-search on it."""
    parts, current = 1, 0
    for x in nums:
        if x > limit:
            return False                          # one element alone exceeds the limit — impossible
        if current + x > limit:
            parts += 1                            # close this part, start a new one with x
            current = x
        else:
            current += x
    return parts <= k
# endregion


# region: binary_answer
def min_largest_sum(nums, k):
    """Minimize the largest part-sum when splitting `nums` into k contiguous parts, by binary
    searching the ANSWER. The answer lies between max(nums) (no part can be smaller than the biggest
    single element) and sum(nums) (one part holds everything). Binary-search that range for the
    smallest limit the greedy check accepts. O(n · log(sum)) — a handful of O(n) checks, not a scan
    of every candidate. Returns the minimized largest-part sum."""
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_split(nums, k, mid):
            hi = mid                              # feasible → try to do even better (smaller)
        else:
            lo = mid + 1                          # infeasible → need a bigger limit
    return lo                                     # lo == hi == the smallest feasible limit
# endregion


# region: isqrt
def integer_sqrt(x):
    """A second, tiny example of the same idea: the integer square root of x is the largest v with
    v*v ≤ x — a monotone predicate (v*v ≤ x is true up to a threshold, false after), so binary-
    search v in [0, x]. O(log x), no floating point, exact."""
    lo, hi, ans = 0, x, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            ans = mid                             # feasible → record it, look for a larger v
            lo = mid + 1
        else:
            hi = mid - 1                          # too big → look smaller
    return ans
# endregion

"""The reference and the contrast. Two ways to solve the split-array problem without binary search:

- `dp_min_largest_sum` is the classic dynamic program — dp[i][j] = the minimized largest sum when
  splitting the first i elements into j parts. It's exact and it's the correctness reference, but
  it's O(n^2 · k), much heavier than the binary-search-on-answer O(n · log(sum)).
- `linear_scan_answer` finds the same threshold by trying EVERY candidate limit from low to high and
  returning the first feasible one. It uses the identical greedy check as binary search, just with a
  linear scan instead of a logarithmic one — the contrast that shows what binary search buys.

Both use the same feasibility predicate; the difference is only how many candidates each tests.
"""
import impl


# region: dp
def dp_min_largest_sum(nums, k):
    """The O(n^2 · k) dynamic program: dp[i][j] = min over the last split point p of max(dp[p][j-1],
    sum(nums[p:i])). Exact, and independent of the binary-search approach, so it's the reference the
    binary-search answer is checked against."""
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    INF = float("inf")
    dp = [[INF] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            for p in range(j - 1, i):             # last part is nums[p:i]
                dp[i][j] = min(dp[i][j], max(dp[p][j - 1], prefix[i] - prefix[p]))
    return dp[n][k]
# endregion


# region: linear
def linear_scan_answer(nums, k):
    """Find the threshold by trying every candidate limit from max(nums) up — the first that passes
    the greedy check is the answer. Same predicate as binary search, O(range) checks instead of
    O(log range). Returns (answer, checks_made)."""
    checks = 0
    for limit in range(max(nums), sum(nums) + 1):
        checks += 1
        if impl.can_split(nums, k, limit):
            return limit, checks
    return sum(nums), checks
# endregion

Desde cero vs librería

La búsqueda binaria sobre la respuesta es el truco que más te abre la cabeza de todo el bloque de paradigmas porque reutiliza un algoritmo conocido para un objetivo desconocido: el único requisito real de la búsqueda binaria es un predicado monótono, y una vez que lo ves, un array ordenado es apenas un caso particular — el espacio de respuestas de un problema de optimización es otro. El replanteo que enseña — "optimizar" se vuelve "decidir, repetidamente" — es ampliamente poderoso, y es la misma descomposición que conecta los problemas de optimización con los de decisión a lo largo de toda la teoría de la complejidad. La brecha de once mil veces del enfrentamiento es la ganancia ordinaria de la búsqueda binaria (partir a la mitad le gana a recorrer) aplicada a un espacio que no sabías que se podía buscar. Además se compone hermoso con los otros paradigmas: la verificación de factibilidad suele ser un algoritmo greedy o una simulación, así que la búsqueda binaria sobre la respuesta muchas veces es "búsqueda binaria envuelta alrededor de un greedy" — dos técnicas de este libro combinándose en una tercera. No hay función de librería porque es una técnica, y la habilidad que construye — reconocer el espacio de respuestas monótono escondido en un problema — es justo el tipo de olfato para patrones que separa el saber algoritmos del diseñarlos.

Dónde te la vas a encontrar

La búsqueda binaria sobre la respuesta aparece dondequiera que haya que optimizar una capacidad, una tasa o un umbral. La planeación de capacidad la usa — el barco, camión o servidor más chico para cumplir una fecha límite o una carga; el ancho de banda mínimo para vaciar una cola a tiempo. La calendarización y la manufactura usan formulaciones de "minimizar el máximo" (balancear el trabajo entre máquinas, minimizar el tiempo de terminación más tardío). El software numérico usa el método de bisección para resolver ecuaciones y hallar raíces donde no existe forma cerrada. Las bases de datos y los sistemas ajustan parámetros (tamaños de buffer, timeouts) haciendo búsqueda binaria sobre un umbral de desempeño. La programación competitiva y las entrevistas técnicas la sacan constantemente, precisamente porque el replanteo de optimización a decisión es una idea reutilizable. El machine learning la usa para calibrar umbrales y encontrar fronteras de hiperparámetros. Los rate limiters, los load balancers y los asignadores de recursos la usan para dimensionar recursos contra una curva de demanda monótona. Dondequiera que la pregunta sea "¿cuál es el recurso mínimo que alcanza?" — y más recurso no perjudique — esta técnica es la respuesta eficiente.

Puntos clave

La búsqueda binaria sobre la respuesta resuelve "encuentra la X más chica/más grande tal que P(X)" aprovechando que P es monótona en X: las respuestas están implícitamente ordenadas por factibilidad, así que le haces búsqueda binaria al umbral, convirtiendo una optimización en O(log rango) verificaciones de factibilidad sí/no fáciles. Hizo que el problema de dividir el array costara 20 verificaciones donde recorrer todos los candidatos costaba 228,000, y vuelve el tamaño del espacio de respuestas casi irrelevante. Los requisitos son un predicado monótono (demuéstralo) y un procedimiento de decisión barato (casi siempre una verificación greedy), y los bugs comunes son las condiciones de frontera, no la idea central. El replanteo — optimizar es decidir repetidamente — es la lección transferible.

Con esto se cierran los paradigmas de diseño de algoritmos: divide y vencerás, greedy, programación dinámica (con la mochila y el alineamiento de secuencias), backtracking, dos punteros y búsqueda binaria sobre la respuesta — las estrategias reutilizables que generan algoritmos, ahora explícitas después de haber aparecido de forma implícita a lo largo del libro. El bloque final regresa a estructuras de datos concretas, pero avanzadas y muchas veces probabilísticas — filtros de Bloom, skip lists, caches LRU, árboles k-d y muestreo de reservorio — estructuras que cambian exactitud o garantías de peor caso por ganancias dramáticas en espacio o simplicidad, y que mueven sistemas reales a gran escala.