Búsqueda binaria sobre el espacio de respuestas
Trate un rango continuo de respuestas como un espacio de búsqueda para resolver problemas como minimum-time-to-complete-jobs y capacity-to-ship-packages.
Búsqueda binaria sobre el espacio de respuestas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Búsqueda binaria en el espacio de respuestas
La mayoría de las personas conoce la búsqueda binaria para encontrar un valor en un array ordenado. Sin embargo, la búsqueda binaria es aún más potente cuando se aplica al espacio de posibles respuestas. En lugar de buscar en un array, se busca en un rango numérico; por ejemplo, «¿cuál es el número mínimo de días necesarios para enviar todos los paquetes?»; y se usa una función de comprobación para decidir si una respuesta candidata es viable.
Esta técnica transforma muchos problemas de optimización de O(n²) o peor a O(n log(max_answer)).
La plantilla del espacio de respuestas
La plantilla tiene tres componentes. Primero, defina el rango de búsqueda [lo, hi] que abarque todas las respuestas válidas. Segundo, escriba una comprobación de viabilidad can_achieve(mid) que devuelva True si el valor mid es alcanzable. Tercero, realice una búsqueda binaria en [lo, hi]: si can_achieve(mid), avance hacia una respuesta menor (o mayor); de lo contrario, avance en la otra dirección.
La propiedad clave es que la función de viabilidad debe ser monótona: una vez que una respuesta es viable, todos los valores posteriores también son viables (o todos los valores inferiores no son viables).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultEjemplo: capacidad para enviar paquetes
LeetCode 1011 «Capacity to Ship Packages Within D Days»: dada una lista de pesos y D días, encuentre la capacidad mínima de envío necesaria para enviar todos los paquetes en orden dentro de D días. La respuesta se encuentra en [max(weights), sum(weights)]. Una capacidad es factible si una simulación greedy permite enviar todos los paquetes dentro de D días. La búsqueda binaria sobre el rango de capacidades tiene una complejidad temporal de O(n log(sum)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Ejemplo: Koko come plátanos
LeetCode 875 «Koko Eating Bananas»: Koko puede comer K plátanos por hora; quiere terminar H montones exactamente en H horas, minimizando K. El rango de búsqueda es [1, max(piles)]. La comprobación es la siguiente: a una velocidad K, el total de horas = sum(ceil(pile/K)), y debe ser <= H. Buscamos mediante búsqueda binaria el K más pequeño que cumpla esta condición.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Ejemplo: días mínimos para hacer ramos
LeetCode 1482 «Minimum Number of Days to Make m Bouquets»: necesita m ramos, cada uno formado por k flores consecutivas que hayan florecido. La flor i florece el día bloomDay[i]. Realice una búsqueda binaria sobre el día: el rango es [1, max(bloomDay)]. La comprobación de factibilidad cuenta las flores consecutivas que han florecido y verifica si se pueden formar m ramos. Propiedad monótona: si el día d funciona, el día d+1 también funciona.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Identificar el rango de búsqueda
Elegir correctamente el rango [lo, hi] es fundamental. lo debe ser la respuesta mínima posible (por ejemplo, el elemento mínimo, 1 o 0) y hi debe ser la respuesta máxima posible (por ejemplo, la suma de todos los elementos, el elemento máximo o n). Establecer hi demasiado pequeño omite respuestas válidas; establecerlo demasiado grande no supone un problema, porque la búsqueda binaria seguirá convergiendo en O(log(hi - lo)) pasos.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Maximizar frente a minimizar: la dirección importa
La búsqueda binaria en el espacio de respuestas tiene dos variantes. Minimizar la respuesta: cuando la comprobación tiene éxito, pruebe valores más pequeños (hi = mid); cuando falla, pruebe valores más grandes (lo = mid + 1). Maximizar la respuesta: cuando la comprobación tiene éxito, pruebe valores más grandes (lo = mid + 1, guardando mid como candidato); cuando falla, pruebe valores más pequeños (hi = mid - 1). Aclare siempre en qué dirección está buscando antes de programar.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Asignar el mínimo de páginas (problema clásico)
Dado un conjunto de n libros con pages[] y k estudiantes, asigne los libros de forma contigua para que el estudiante que lea más páginas lea el menor número posible. Realice una búsqueda binaria sobre la respuesta (el máximo mínimo posible). La comprobación de factibilidad asigna los libros de forma greedy: cuando añadir un libro superaría el máximo actual, asígnelo a un estudiante nuevo. Si se necesitan <= k estudiantes, ese máximo es alcanzable.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Análisis de complejidad de la búsqueda en el espacio de respuestas
La complejidad temporal es O(n × log(range)), donde n es el coste de la comprobación de factibilidad (normalmente un recorrido lineal) y range = hi - lo (el tamaño del espacio de respuestas). Por ejemplo, si la suma de las páginas es 10⁹ y la comprobación de factibilidad es O(n), el tiempo total es O(n log 10⁹) ≈ O(30n), mucho mejor que la fuerza bruta O(n²).
La complejidad espacial es O(1) para la búsqueda binaria en sí, además de la que utilice la comprobación de factibilidad.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')K-ésimo menor en una matriz ordenada
LeetCode 378 «Kth Smallest Element in a Sorted Matrix»: cada fila y columna de una matriz n×n está ordenada. Realice una búsqueda binaria sobre el valor de la respuesta en [matrix[0][0], matrix[n-1][n-1]]. La comprobación de factibilidad cuenta los elementos <= mid mediante un puntero que comienza en la esquina inferior izquierda, con un coste de O(n). Encuentre el valor más pequeño tal que al menos k elementos sean <= mid.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Reconocer problemas del espacio de respuestas
Los problemas adecuados para la búsqueda binaria en el espacio de respuestas comparten algunas señales: la pregunta pide un valor mínimo o máximo, la respuesta se encuentra en un rango numérico acotado y aumentar (o disminuir) la respuesta candidata hace que la factibilidad mejore o empeore de forma monótona. Entre las palabras clave habituales están «minimum possible maximum», «at most k operations» y «within d days».
Cuando detecte estas señales, defina inmediatamente lo y hi, escriba la función de factibilidad y aplique la plantilla. Este enfoque estructurado rara vez falla en las entrevistas.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección ha aprendido que: la búsqueda binaria en el espacio de respuestas se aplica cuando una función de factibilidad es monótona sobre un rango numérico, la plantilla busca en [lo, hi] y utiliza una comprobación can_achieve para dividir el espacio de búsqueda por la mitad y la complejidad total es O(n log(range)), donde n es el coste de una comprobación de factibilidad. A continuación pasaremos a las listas enlazadas y a la clase Node.
Preguntas frecuentes
¿La lección «Búsqueda binaria sobre el espacio de respuestas» es gratis?
Sí — el texto completo de «Búsqueda binaria sobre el espacio de respuestas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Búsqueda binaria sobre el espacio de respuestas»?
Trate un rango continuo de respuestas como un espacio de búsqueda para resolver problemas como minimum-time-to-complete-jobs y capacity-to-ship-packages. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Búsqueda binaria sobre el espacio de respuestas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Búsqueda binaria clásica: izquierda, derecha y centro
- Búsqueda binaria en arrays rotados y sin ordenar
- Límite inferior y límite superior
- Búsqueda binaria sobre el espacio de respuestas