Tras el gran éxito de sus estrenos anteriores, Algoritmos de ordenamiento y Algoritmos de redondeo, teknoPLOF! vuelve al ataque con su tercera entrega Algoritmos de búsqueda básicos para torpes (<- este último metavínculo es recursivo en sí mismo; miedito).

Los programadores informáticos son muy cuadriculados y todo lo tienen que hacer siguiendo unas pautas prefijadas perfectamente determinadas y secuenciadas. Paso 1, paso 2 y paso 3; y fin del asunto. Como suelen utilizar enormes cantidades de datos (yo que sé, como inmensas listas de personas con sus teléfonos, por ejemplo), se les hace necesario poder buscar un elemento en concreto dentro de un grupo de ellos. Y eso, a veces, no es tan sencillo.

Hoy en día existen métodos de búsqueda propios y muy optimizados en los lenguajes de programación más modernos y, también, en los propios gestores de datos. Sin embargo, no viene mal conocer los algoritmos de búsqueda más básicos del mundo mundial por si se nos presenta esa ocasión eventual en la que tenemos cosas que ordenar y no disponemos de herramientas a nuestra disposición.

Y, además, lo vamos a hacer de una manera tan insultantemente sencilla que resulta hasta ofensiva. Pero bueno, allá vamos.

Búsqueda secuencial (lineal)

Es tan fácil como recorrer, secuencialmente, toda la lista de elementos en la que queremos buscar uno en concreto (llamado clave) desde el principio hasta el final. Si lo encontramos, ¡estupendo!, si no lo encontramos es que no está. Tan sencillo como eso.

La búsqueda secuencial se utiliza para listas o matrices de datos que están desordenadas, que no siguen un orden en concreto, como un listado de alumnos de un colegio, por ejemplo, que no está ordenado alfabéticamente.

Dado que, como decimos, el conjunto no tiene un orden prefijado, es probable que el elemento que estamos buscando se encuentre en primera posición, que esté el último o que ande por el medio de la lista (¡o que no esté!). Por ello, este tipo de búsqueda puede ser mu rpdilla o hacerse eteeeeeeeeerna, en función del número de elementos en el grupo. Funciona correctamente en listas cortitas y es muy sencillo de implementar.

Búsqueda binaria (dicotómica)

El algoritmo de búsqueda binaria es mucho más eficaz que el de búsqueda secuencial, pero eso sí, necesita que la lista de datos esté ordenada; por ejemplo, un índice de pueblos organizados numéricamente, de menor a mayor, por su código postal.

Los pasos que se deben seguir son muy sencillos. Se empieza a buscar el dato que necesitamos encontrar por el elemento de en medio de la lista, el del centro. Si no es el que buscamos, comprobamos qué relación tiene con él, es decir, si es mayor o menor. Si es menor, por ejemplo, acotamos la búsqueda a la primera mitad de la lista. Y repetimos: cogemos el elemento central y lo comparamos con el que estamos buscado; si no es, volvemos a acotar la búsqueda en función de si el que buscamos es mayor o menor que el nuevo central.

Un ejemplo facilón para que quede claro. Dada la siguiente lista de valores numéricos ordenados:

2 23 35 38 47 56 57 76 83 85 90 92 95 98 99

Quiero saber si el número 56 se encuentra en la lista. Leo el valor central de la lista: 76. ¿Es el que busco? No. ¿Es mayor o menor que el que busco? Mayor. Por lo tanto me quedo con una lista más pequeña, la que va de 2 a 57. Leo, otra vez, en valor central: 38. ¿Es el que busco? No. ¿Es mayor o menor que el que busco? Menor. Entonces, mi nueva lista para comparar es de 47 a 57. Vuelvo a leer el valor central: 56. ¿Es el que busco? Sí. Finiquitado en tres comparaciones.

En el caso de que, en algún momento, alguna de las listas tenga un número par de elementos, no pasa nada, los programadores son tan listos que ellos se encargan de realizar labores de redondeo a la hora de averiguar la parte media de una relación.

Búsqueda por interpolación

Este último tipo de búsqueda es un poco más puñetero. En principio es muy parecido al anterior, pues es un algoritmo recursivo (se repite continuamente hasta que da con el valor buscado) y también acota las listas en secciones más pequeñas. La diferencia con la búsqueda binaria es que, en lugar de cortar las listas todo el rato por la mitad, éstas se delimitan siempre por medio de los valores resultantes de una interpolación matemática. Más clarito: si durante la búsqueda encontramos un valor que está muy cerca del número clave que buscamos, parece más razonable continuar buscando en esa área, en lugar de cortar y buscar el número central otra vez.

En matemáticas, se denomina interpolación a la obtención de nuevos valores partiendo del conocimiento de un conjunto de otros valores. Fijémonos de nuevo en la lista anterior. Tras la primera comparación apuntando al centro, la nueva lista que nos quedaba iba de 2 a 57. El número que andaba buscando era el 56, que está terriblemente cerquita del final de mi lista; tan cerquita, tan cerquita que casi se tocan. La lógica me dice que voy a andar mejor empezando a buscar por el final que tirando al centro y comparando de nuevo.

Los programadores utilizan esas interpolaciones matemáticas, codificadas en código fuente de un lenguaje de programación, para determinar por dónde andan los valores más cercanos y afinar la búsqueda.

Y hemos llegado al final. Existen otros algoritmos de búsqueda, pero estos son los más simples y los más utilizados. Y no vamos a escribir ni una sola línea de código porque nos hemos prometido hacerlo fácil de entender. Los informáticos que deseen codificar estas explicaciones, no creo yo que tengan ningún problema en hacerlo rápidamente; es extremadamente sencillo.

Se acabó.