Al cerrar el módulo 5 dijimos que el éxito de TareaFácil traía consigo el mejor tipo de problema: cuando la agenda de Estudio Alba tenga doscientas tareas guardadas en tareas.json, «buscar la del cliente Vidal» dejará de ser trivial. Hasta ahora hemos usado in, .index() y la pertenencia en conjuntos como cajas negras: funcionan, y no hemos preguntado cómo. Esta lección abre la primera de esas cajas.

Buscar es, con diferencia, la operación más frecuente de cualquier programa que maneje datos. Aquí aprenderás las tres familias de técnicas que existen —búsqueda lineal, búsqueda binaria y búsqueda por clave—, qué exige cada una, cuánto cuesta y cuándo elegirla. Las implementaremos a mano para entenderlas por dentro, con la misma moraleja honesta de siempre: en producción se usa la herramienta del lenguaje.

1. Qué significa buscar y qué se devuelve
2. Búsqueda lineal: el algoritmo de referencia
3. Trazado paso a paso de la búsqueda lineal
4. Búsqueda con criterio: el callback vuelve
5. Buscar todas las coincidencias
6. Búsqueda binaria: la idea de descartar la mitad
7. Búsqueda binaria: implementación y trazado
8. Lineal frente a binaria
9. Búsqueda por clave: diccionarios y conjuntos
10. Índice invertido: preparar la búsqueda
11. TareaFácil v0.12: tres formas de localizar una tarea
12. Errores comunes y consejos
13. Ejercicios
14. Conclusión

«Buscar» parece una sola cosa y en realidad son tres preguntas distintas, y confundirlas es el primer error del principiante:

En una lista de números las tres coinciden casi siempre. En nuestra agenda —una lista de diccionarios— la diferencia es enorme: saber que existe una tarea de Nuria no me sirve para cambiarle la prioridad; para eso necesito el diccionario, o al menos su posición.

Y hay una cuarta decisión: qué pasa cuando no se encuentra nada. Los tres convenios habituales son devolver -1 (tradición heredada de C y Java), devolver None (lo idiomático en Python cuando se devuelve un elemento) o lanzar un error, que es lo que hace .index() con su ValueError. Usaremos -1 para posiciones y None para elementos. Sea cual sea el convenio, documéntalo en el docstring y sé coherente en todo el programa.

La búsqueda lineal (o secuencial) es el algoritmo más simple que existe: mirar los elementos uno por uno, desde el principio, hasta encontrar el que buscas o agotar la colección. No exige absolutamente nada de los datos: sirven ordenados o desordenados, en una lista, en un fichero o en una cinta.

Traducido a Python sobre nuestra agenda, con enumerate de 05-01 para tener a la vez posición y elemento:

Tres detalles hacen bueno a este código. La salida temprana con return: en cuanto encuentra la tarea, la función termina; si guardáramos el resultado en una variable y siguiéramos recorriendo, en una agenda de 200 tareas miraríamos 199 de más. El return -1 está fuera del bucle, alineado con el for: solo se llega ahí cuando el recorrido ha terminado sin encontrar nada; puesto dentro, la función devolvería -1 en la primera vuelta que no coincidiera. Y la comparación es ==, no in: exige coincidencia exacta, y ya veremos la variante «contiene» en la sección 4.

Las dos funciones son idénticas salvo en lo que devuelven, la posición o el elemento. Y recuerda el aliasing de 05-01: lo que devuelve la segunda es el mismo diccionario que está en la lista, así que buscar_tarea(agenda, "Cartel feria")["prioridad"] = "baja" modifica la agenda de verdad. Es el mecanismo en el que ya se apoyaba elegir_tarea desde la v0.10.

Hagamos la prueba de escritorio de 01-05 sobre esta agenda de Estudio Alba:

Trazamos dos casos a la vez: A, buscar "Logotipo cliente Vidal", que sí está; y B, buscar "Flyer verano", que no existe.

El caso A termina en tres comparaciones y la posición 3 no se llega a mirar: ese es el efecto de la salida temprana. El caso B necesita cuatro, es decir, todas. Y ahí está la primera lección de coste del módulo, que se lee directamente de la tabla. Mejor caso: el elemento está el primero, una comparación. Peor caso: está el último o no está, tantas comparaciones como elementos. Caso medio: la mitad de los elementos. Retén el detalle importante: el peor caso de la búsqueda lineal es no encontrar nada, así que un programa que busca a menudo cosas inexistentes está en el peor escenario posible para este algoritmo.

Las funciones anteriores solo saben buscar por título exacto. Si Marta quiere buscar por responsable, por prioridad o por «títulos que contengan la palabra feria», ¿escribimos una función por caso? No: aplicamos el patrón callback de 04-05, y en vez del valor a comparar, la función recibe la comprobación en forma de función.

El esqueleto del recorrido lo pone buscar_si; la decisión de qué cuenta como «encontrado» la pone quien llama. La tercera línea usa el in de cadenas de 05-02 —«contiene»— y .lower() para no distinguir mayúsculas, que es lo que espera cualquier usuario; la cuarta combina dos condiciones sin que buscar_si se entere. Python trae esta idea incorporada en next con una expresión generadora:

Se lee «el siguiente elemento de la agenda cuyo responsable sea Nuria, o None si no hay ninguno». Sin ese segundo argumento, next lanza un error cuando no hay coincidencias. Es la forma idiomática y perezosa —deja de recorrer en cuanto encuentra, igual que nuestro return— y la que usarías en un proyecto real. buscar_si existe para que veas que por dentro no hay magia: es un for con un if.

A veces no quieres la primera, quieres todas: «todas las tareas de Luis», «todas las de prioridad alta». El algoritmo cambia en un punto esencial: no hay salida temprana, porque hay que examinar la colección entera.

La comprensión es la opción preferente por legibilidad. Y ojo a la última línea: si solo necesitas cuántas hay, cuenta directamente en vez de construir una lista que ibas a tirar.

Si los datos están ordenados, se puede hacer algo mucho mejor que mirar uno por uno. Piensa en cómo buscas una palabra en un diccionario de papel: no empiezas por la A, lo abres por la mitad, ves en qué letra estás y descartas media obra de un golpe. Ese es el algoritmo de búsqueda binaria, y su requisito es innegociable: la colección debe estar ordenada según el mismo criterio por el que buscas. Si no lo está, la búsqueda binaria no da error, da respuestas incorrectas, que es mucho peor.

Sobre esta lista ordenada de códigos de encargo de Estudio Alba —[102, 118, 134, 156, 170, 189, 203, 240], posiciones 0 a 7— buscamos el 170:

Tres comparaciones para ocho elementos, frente a las cinco de la lineal. La diferencia parece modesta aquí; con un millón es abismal, y lo veremos numéricamente en la sección 8.

El algoritmo mantiene tres variables: izquierda y derecha delimitan el trozo donde el valor todavía podría estar, y medio es la posición que se examina en cada vuelta.

Cuatro puntos donde se rompe este algoritmo, y hay que entenderlos con precisión:

• while izquierda <= derecha, con el igual. Cuando ambos coinciden queda un elemento por mirar, y hay que mirarlo. Con < a secas fallarían justo los valores que quedan solos al final del trozo.
• (izquierda + derecha) // 2 usa la división entera de 02-02: si la suma es impar se redondea hacia abajo. Da igual hacia qué lado, siempre que el trozo se reduzca cada vuelta.
• medio + 1 y medio - 1, nunca medio a secas. Ya hemos comprobado que valores[medio] no es el buscado, así que se descarta también él. Con izquierda = medio, el trozo deja de encoger cuando quedan dos elementos y el programa se queda colgado en un bucle infinito.
• El trozo se reduce a la mitad en cada vuelta, y por eso el bucle siempre termina: o encuentra el valor, o izquierda acaba pasando a derecha.

Trazamos dos búsquedas sobre la lista de códigos, una fila por vuelta del while: el 170, que está, y el 150, que no.

Fíjate en las dos terceras vueltas: en ambas izquierda y derecha valen lo mismo, el bucle sí entra y examina el último candidato. Solo después izquierda supera a derecha y el bucle termina. Es la mejor demostración de que el <= no es un detalle cosmético.

Existe también una versión recursiva de este algoritmo, más corta y para muchos más elegante, que escribiremos en Recursión cuando tengamos la herramienta. Y, como siempre, Python ya trae esto hecho: el módulo bisect de la biblioteca estándar implementa la búsqueda binaria en C, y su función bisect.insort(lista, valor) inserta manteniendo el orden. En producción se usa bisect; esta implementación es para entender qué hace por dentro.

Los números salen de una regla sencilla: cada vuelta de la binaria divide entre dos el trozo pendiente, así que doblar los datos le añade una sola comparación. Pasar de mil a un millón de elementos multiplica por mil el trabajo de la lineal y le suma diez comparaciones a la binaria; el nombre formal de esa diferencia lo pondremos en Eficiencia y notación Big-O. Pero la tabla también avisa de la letra pequeña: ordenar cuesta. Si vas a buscar una sola vez en una lista desordenada, ordenarla para poder usar la binaria sale más caro que recorrerla entera. La binaria compensa cuando la colección ya está ordenada o cuando vas a buscar muchas veces.

Queda la técnica más rápida de las tres, la que ya llevas usando desde 05-03 sin saber cómo funciona. Preguntar "Marta" in equipo o leer ficha["rol"] no recorre nada y no compara nada: encuentra el dato de un salto, tenga el diccionario diez claves o diez millones. El mecanismo se llama tabla hash, y la idea intuitiva, sin entrar en el detalle, es esta: Python aplica a la clave una función matemática —la función hash— que la convierte siempre en el mismo número; ese número indica en qué casilla de una tabla interna vive el par clave-valor; y para buscar se repite el cálculo y se va directamente a esa casilla, sin recorrer nada.

Esa es también la explicación del requisito de 05-03: las claves de un diccionario y los elementos de un conjunto deben ser inmutables. Si usaras una lista como clave y luego la modificaras, su hash cambiaría, la casilla calculada sería otra y el dato quedaría guardado en un sitio donde nadie va a mirar. El resumen práctico es contundente:

La conclusión operativa la anticipamos en 05-03 y ahora ya sabes por qué: si tu programa hace muchas comprobaciones de pertenencia sobre una colección, esa colección debería ser un conjunto o un diccionario, no una lista. El precio es memoria extra y la pérdida del orden de inserción como criterio de búsqueda.

Aquí llega la idea que convierte todo lo anterior en una decisión de diseño. Si Marta va a preguntar quince veces al día «¿qué tiene Luis?», recorrer la agenda entera quince veces es absurdo: mejor recorrerla una vez y construir un diccionario que responda al instante. Esa estructura se llama índice invertido: en vez de ir de la tarea a su responsable, va del responsable a sus tareas.

El patrón if nombre not in indice: indice[nombre] = [] es el mismo «primera vez» de 05-03, y también se escribe en una línea con indice.setdefault(nombre, []).append(tarea). indice.get("Luis", []) devuelve una lista vacía si esa persona no tiene nada, evitando el KeyError.

Esto es un intercambio: gastamos memoria y un recorrido previo para que las consultas posteriores sean inmediatas. Compensa cuando se consulta mucho y se modifica poco; no compensa cuando la agenda cambia sin parar, porque el índice queda obsoleto en cuanto se registra una tarea nueva. Es la primera aparición del intercambio tiempo-memoria, que estudiaremos con nombre propio en 06-04.

Añadimos al programa una opción de búsqueda que usa las tres técnicas según el caso: por título exacto cuando Marta sabe qué busca, por texto contenido cuando solo recuerda una palabra, y por responsable con índice cuando quiere el reparto. El menú pasa a ocho opciones.

Decisiones de diseño que merece la pena señalar:

• buscar_si y buscar_todas no saben nada de tareas. Reciben el criterio como callback, así que sirven para cualquier colección de diccionarios; toda la lógica específica vive en las lambda de menu_buscar.
• menu_buscar es la única que habla con el usuario, cumpliendo la separación entre entrada/salida y lógica de 04-04. Las funciones de búsqueda no imprimen nada, y las tres ramas confluyen en una única lista halladas que se muestra igual en los tres casos. Además, la búsqueda por texto pasa ambos lados a minúsculas, de modo que «vidal», «Vidal» y «VIDAL» encuentran lo mismo.
• El índice se construye dentro de la rama 3 y se descarta al salir. Es deliberado: la agenda cambia entre consulta y consulta, y un índice guardado en una global se quedaría obsoleto. Con veinte tareas, reconstruirlo cuesta un suspiro.

No hay búsqueda binaria en TareaFácil, y es una decisión consciente: la agenda no está ordenada por título, y ordenarla solo para poder buscar sería más caro que recorrerla. Con veinte tareas, la lineal es la respuesta correcta.

Poner el return de «no encontrado» dentro del bucle. Es el error número uno de la lección: la función devuelve -1 o None en la primera vuelta que no coincide, sin mirar el resto. Ese return va fuera del for, a su misma altura.

Olvidar comprobar el resultado. Si buscar_tarea devuelve None y escribes tarea["prioridad"], obtienes TypeError: 'NoneType' object is not subscriptable. Comprueba siempre con if tarea is not None: antes de usar lo devuelto. Y usar búsqueda binaria sobre datos sin ordenar no falla con un error, falla con un resultado equivocado: dice que un elemento no está cuando sí está. Si tu función exige orden, dilo en el docstring. Escribir izquierda = medio en vez de medio + 1 hace que el trozo deje de encoger y el programa se cuelgue en un bucle infinito; si tu binaria se queda parada, mira ahí primero.

Confundir == con in al buscar textos. t["titulo"] == "feria" solo encuentra una tarea que se llame exactamente así; "feria" in t["titulo"] encuentra todas las que la contengan.

Consejo: normaliza antes de comparar. Aplica .strip().lower() a los dos lados cuando busques texto escrito por una persona: un espacio final es invisible y hace fallar la comparación.

Consejo: en producción, la herramienta del lenguaje. in, .index(), next(...), una comprensión, un diccionario o bisect están escritos en C, probados por millones de programas y son más rápidos que cualquier bucle que escribas. Estas implementaciones existen para que entiendas qué hacen por dentro y sepas cuál elegir, no para copiarlas a tu proyecto.

Sobre la lista ordenada [2, 5, 9, 14, 21, 30, 44, 51, 68] (posiciones 0 a 8), traza en una tabla la búsqueda binaria de los valores 44 y 7, indicando en cada vuelta izquierda, derecha, medio, el valor examinado y la acción. Di cuántas comparaciones necesita cada búsqueda y cuántas habría necesitado la búsqueda lineal.

Escribe tres funciones sobre la agenda (lista de diccionarios con titulo, responsable, prioridad, dias, completada):

• primera_urgente(agenda): devuelve la primera tarea pendiente de prioridad alta, o None.
• pendientes_de(agenda, nombre): devuelve la lista de tareas pendientes de esa persona, sin distinguir mayúsculas.
• hay_bloqueo(agenda): devuelve True si alguien tiene más de tres tareas pendientes. Debe apoyarse en un índice, no en un bucle anidado.

Escribe indice_por_prioridad(agenda) que devuelva un diccionario con las claves "alta", "media" y "baja" —las tres siempre presentes, aunque alguna esté vacía— y como valor la lista de títulos de las tareas pendientes de esa prioridad. Después, escribe informe(indice) que imprima cada prioridad con su número de tareas y sus títulos.

Solución 1.

Dos comparaciones para el 44 (la lineal habría necesitado siete) y tres para el 7 (la lineal, las nueve del recorrido completo, porque no está). Fíjate en la asimetría: la binaria tarda casi lo mismo encuentre o no, mientras que a la lineal el fracaso le cuesta siempre el máximo.

Solución 2.

hay_bloqueo recorre la agenda una sola vez construyendo un índice de recuentos, en vez de recorrerla una vez por cada miembro del equipo. Con tres personas la diferencia es irrelevante; con trescientas, es la diferencia entre un programa usable y uno que no lo es. any devuelve True en cuanto encuentra un valor que cumple la condición y deja de mirar: es la salida temprana de la sección 2, ya incorporada al lenguaje.

Solución 3.

La clave está en la primera línea: {p: [] for p in PRIORIDADES} es una comprensión de diccionario que crea las tres claves de antemano usando la constante PRIORIDADES. Gracias a eso el bucle puede hacer indice[...].append(...) sin comprobar nada, e informe recorre las prioridades en su orden lógico —alta, media, baja— en vez del orden en que aparecieran en la agenda. Elegir bien la estructura simplifica el código que viene después.

Buscar no es una operación, son tres preguntas: si existe, dónde está y cuál es; y una cuarta decisión, qué devolver cuando no hay nada (-1, None o un error). La búsqueda lineal recorre uno por uno con salida temprana mediante return: no exige nada de los datos, encuentra en una comparación en el mejor caso y necesita recorrerlo todo en el peor, que es precisamente cuando el elemento no está. Convertida en función de orden superior con un callback, la misma función busca por título, por responsable o por texto contenido; y sin salida temprana se transforma en la búsqueda de todas las coincidencias, que en Python se escribe con una comprensión de lista.

La búsqueda binaria cambia recorrer por descartar: exige datos ordenados y en cada vuelta parte el problema en dos, de modo que un millón de elementos se resuelven en veinte comparaciones. Sus tres trampas son el while izquierda <= derecha, el (izquierda + derecha) // 2 y el medio + 1 / medio - 1 que garantizan que el trozo encoge. Y la búsqueda por clave en diccionarios y conjuntos gana a las dos anteriores gracias a la tabla hash, que calcula la casilla en vez de comparar; de ahí que las claves deban ser inmutables. Cuando una consulta se repite mucho, merece la pena pagar un recorrido y algo de memoria para construir un índice invertido. Y en producción, siempre, la herramienta del lenguaje: in, .index(), next, una comprensión, un diccionario o bisect. TareaFácil llega a la v0.12 y Marta ya puede preguntarle a su agenda. Pero la búsqueda binaria se ha quedado sin usar por una razón concreta: la agenda no está ordenada, y ordenarla es justo lo que hemos estado delegando en sorted sin preguntar. En Algoritmos de ordenamiento abriremos esa segunda caja negra: qué hace sorted por dentro, qué significa que una ordenación sea estable y por qué ordenar es la operación más rentable de todo el curso.