First True: búsqueda binaria por predicado
Busque un límite monótono de sí o no
First True: búsqueda binaria por predicado es una lección gratuita de Competitive Programming Academy en CoddyKit. Esta es la lección 3 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.
Busque un límite de sí/no
Muchos problemas esconden un predicado monótono: false, false y después true para siempre. La búsqueda binaria puede encontrar ese primer true sin necesidad de un array ordenado.
# FFFFTTTT -> find first TQué significa monótono
Un predicado es monótono cuando, una vez que se vuelve true, permanece en true. Esa única propiedad permite buscar el límite mediante búsqueda binaria.
def ok(x):
return x * x >= targetDelimite el espacio de respuestas
Elija un rango que contenga con seguridad el límite. Establezca low en el candidato más pequeño y high en un valor para el que ok sea sin duda true.
low, high = 0, 10**9Pruebe el punto medio
Tome mid y llame a ok(mid). El resultado booleano le indica qué mitad conservar, igual que al comparar un valor en una búsqueda binaria normal.
mid = (low + high) // 2
if ok(mid):
...True significa que quizá sea menor
Si ok(mid) es true, mid es una respuesta válida, pero quizá también funcione una menor. Conserve mid estableciendo high = mid, no mid - 1.
if ok(mid):
high = midFalse significa subir
Si ok(mid) es false, el límite está por encima de mid. Descarte mid y todo lo que haya por debajo con low = mid + 1.
else:
low = mid + 1Bucle mientras low sea menor que high
Use while low < high, no menor o igual. Los dos punteros convergen en el primer índice true y entonces el bucle se detiene.
while low < high:
mid = (low + high) // 2La respuesta es low
Cuando termina el bucle, low es igual a high y ambos apuntan al valor del primer true. Devuelva low como el límite que buscaba.
return low # first x where ok(x)Por qué funciona high = mid
Como mid puede ser la respuesta, no debe omitirlo. Usar high = mid lo mantiene dentro del rango y, al mismo tiempo, lo reduce, garantizando el progreso.
high = mid # mid stays a candidateEjemplo de raíz cuadrada entera
Para encontrar el mayor x cuyo cuadrado x*x sea como máximo n, busque el primer true de x*x > n y después retroceda una posición. El patrón se reutiliza.
def ok(x):
return x * x > n
# answer is found_index - 1Una plantilla, muchos problemas
Esta plantilla de primer true resuelve innumerables tareas: encontrar el valor mínimo viable, el índice más a la izquierda o la capacidad más pequeña. Apréndala una vez y reutilícela en todas partes.
# low<high, ok->high=mid, else low=mid+1Comprobación rápida
Determine el movimiento que mantiene vivo al candidato.
Repaso: encuentre el primer true
Ya puede convertir un problema en un predicado monótono y buscar el límite mediante búsqueda binaria. high = mid junto con while low < high es el patrón seguro. 🧭
Preguntas frecuentes
¿La lección «First True: búsqueda binaria por predicado» es gratis?
Sí — el texto completo de «First True: búsqueda binaria por predicado» 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 «First True: búsqueda binaria por predicado»?
Busque un límite monótono de sí o no 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 3 de 4.
¿Cuánto tiempo toma la lección «First True: búsqueda binaria por predicado»?
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