Búsqueda binaria sobre la respuesta
Suponga el resultado y compruebe si es viable
Búsqueda binaria sobre la respuesta es una lección gratuita de Competitive Programming Academy 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
Suponga y verifique
A veces no puede calcular directamente la respuesta, pero sí puede comprobar una suposición. La búsqueda binaria sobre la respuesta convierte una optimización difícil en una comprobación sencilla.
# guess X, ask: is X feasible?La propiedad clave
Funciona cuando la viabilidad es monótona: si un valor funciona, todos los valores mayores (o menores) también funcionan. Ese orden es lo que se busca.
# feasible(X) true => feasible(X+1) trueDelimite el rango de respuestas
Identifique las respuestas mínima y máxima posibles como low y high. Para una capacidad mínima, low es un elemento y high es la suma total.
low, high = max(weights), sum(weights)Escriba la comprobación de viabilidad
El núcleo del método es una función can(X) que devuelve true si la suposición X es alcanzable. Normalmente se ejecuta en tiempo lineal.
def can(cap):
# simulate and return True/False
...Ejemplo: enviar en D días
Dada la capacidad diaria cap, llene los días de forma voraz y cuéntelos. can(cap) es true cuando el número de días se mantiene dentro del límite D.
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= DBusque la capacidad mínima
Busca la cap más pequeña que lo supera. Esta es una búsqueda de primer true sobre las capacidades, así que reutilice la plantilla high = mid.
while low < high:
mid = (low + high) // 2Conserve la mitad viable
Si can(mid) es true, quizá siga funcionando una capacidad menor, así que establezca high = mid. En caso contrario, eleve el límite inferior con low = mid + 1.
if can(mid):
high = mid
else:
low = mid + 1Tenga en cuenta el límite de tiempo
El coste total es O(check x log range). Una comprobación lineal sobre un rango de mil millones de valores requiere solo unas 30 comprobaciones, lo bastante rápido para límites estrictos.
# log2(1e9) is about 30 iterationsMaximice en lugar de minimizar
Para encontrar el valor viable más grande, invierta la lógica: busque el último true. Aumente low cuando sea viable y reduzca high cuando no lo sea.
if can(mid):
low = mid
else:
high = mid - 1Respuestas de valor real
Para respuestas en coma flotante, repita un número fijo de veces, como 100, en lugar de calcular un mid entero. Cada ronda divide el intervalo por la mitad y alcanza rápidamente una precisión muy alta.
for _ in range(100):
mid = (low + high) / 2Detecte el patrón
Expresiones como mínimo del máximo, máximo del mínimo o el menor k que funciona son señales de que debe buscar la respuesta mediante búsqueda binaria. Entrene la vista para reconocerlas.
# 'minimize the maximum' => search answerComprobación rápida
Decida cuándo es aplicable la búsqueda binaria sobre la respuesta.
Repaso: busque la respuesta
Ya puede delimitar la respuesta, escribir una comprobación de viabilidad y buscar mediante búsqueda binaria el mínimo o el máximo. Los problemas difíciles se convierten en suponer y verificar. 🏆
Preguntas frecuentes
¿La lección «Búsqueda binaria sobre la respuesta» es gratis?
Sí — el texto completo de «Búsqueda binaria sobre la respuesta» 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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Búsqueda binaria sobre la respuesta»?
Suponga el resultado y compruebe si es viable Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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 la respuesta»?
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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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 sin errores
- bisect_left y bisect_right
- First True: búsqueda binaria por predicado
- Búsqueda binaria sobre la respuesta