Buscar con un invariante
Usa el orden para descartar respuestas imposibles sin perder la correcta.
AL TERMINAR, PODRÁS
- Explicar por qué la búsqueda binaria exige una entrada ordenada
- Mantener un intervalo de búsqueda semiabierto
- Manejar a propósito los valores ausentes y los duplicados
Descripción del diagrama: 3, 8, 12, 19, 27, 31, 44, 50; el objetivo 19 aún puede estar aquí: 0–3; 0: lo; 2: mid: 12 < 19; 4: hi (excluido)
El orden da información
Una búsqueda lineal revisa elementos hasta encontrar una coincidencia o llegar al final.
La búsqueda binaria (binary search) aprovecha el orden: compara el valor del medio y descarta la mitad que no puede contener la respuesta. El número de comparaciones crece de forma logarítmica, pero solo porque la suposición de orden es cierta. Ordenar solo para una búsqueda puede costar más que recorrer una vez.
La búsqueda binaria vale la pena cuando los datos ya están ordenados o cuando muchas búsquedas reutilizan ese orden. Identifica cuánto cuesta mantener el orden a medida que llegan registros nuevos.
Define el intervalo con precisión
Es más fácil razonar sobre una implementación cuando su región de candidatos está definida con precisión.
Con un intervalo semiabierto [lo, hi), lo está incluido y hi está excluido, así que la región queda vacía cuando lo es igual a hi. El bucle se repite mientras lo < hi: si el valor del medio es demasiado pequeño, haz lo = mid + 1; si no, haz hi = mid. Cada iteración debe reducir la región sin descartar una respuesta válida posible. bisect_left de Python devuelve la posición de inserción antes de los valores iguales que ya existan.
No promete que exista un valor que coincida. Compara el índice devuelto con la longitud de la colección y revisa el elemento antes de afirmar que la búsqueda tuvo éxito.
from bisect import bisect_left
ids = [10, 20, 20, 40]
i = bisect_left(ids, 20)
found = i < len(ids) and ids[i] == 20
print(i, found)Buscar es una decisión de diseño
La respuesta que quieres cambia el algoritmo.
¿Quieres cualquier ID que coincida, el primer duplicado, todos los duplicados o la siguiente hora programada después de un umbral? Deja claro ese contrato antes de elegir código. Prueba una colección vacía, un objetivo antes del primer elemento, uno después del último y los duplicados.
En Relay, un calendario ordenado podría encontrar eficientemente el primer trabajo futuro, pero insertar en una lista de Python sigue desplazando elementos. Una búsqueda rápida no hace rápida toda la estructura de datos.
ERROR FRECUENTE
Tratar una posición de inserción como prueba de una coincidencia, o ignorar el costo O(n) de insertar en una lista ordenada de Python.
INTÉNTALO TÚ
Para [2, 5, 5, 9], predice las posiciones de bisect_left para 1, 5, 8 y 10. Identifica cuáles corresponden a coincidencias reales.
Decide en el laboratorio.
El checkpoint de dos preguntas, tus notas y tu progreso guardado están en el laboratorio. Gratis y sin cuenta.
Abrir en el laboratorio ↗CONÉCTALO CON RELAY
Implementa una búsqueda de trabajos programados de Relay y anota si devuelve un trabajo, un punto de inserción o ambos.