Introducción

La búsqueda de datos almacenados en diferentes estructuras de datos es una parte crucial de casi todas las aplicaciones.

Hay muchos algoritmos diferentes disponibles para utilizar al buscar, y cada uno tiene diferentes implementaciones y se basan en diferentes estructuras de datos para hacer el trabajo.

Ser capaz de elegir un algoritmo específico para una tarea determinada es una habilidad clave para los desarrolladores y puede significar la diferencia entre una aplicación rápida, fiable y estable y una aplicación que se desmorona por una simple petición.

• Operadores de pertenencia
• Búsqueda lineal
• Búsqueda binaria
• Búsqueda por salto
• Búsqueda Fibonacci
• Búsqueda exponencial
• Búsqueda por interpolación

Operadores de pertenencia

Los algoritmos se desarrollan y optimizan con el tiempo como resultado de la constante evolución y la necesidad de encontrar las soluciones más eficientes para los problemas subyacentes en diferentes dominios.

Uno de los problemas más comunes en el dominio de la Informática es buscar en una colección y determinar si un objeto dado está presente en la colección o no.

Casi todos los lenguajes de programación tienen su propia implementación de un algoritmo de búsqueda básico, normalmente como una función que devuelve un valor Boolean de True o False cuando se encuentra un elemento en una colección dada de elementos.

En Python, la forma más fácil de buscar un objeto es utilizar los Operadores de Membresía – llamados así porque nos permiten determinar si un objeto dado es un miembro en una colección.

Estos operadores se pueden utilizar con cualquier estructura de datos iterable en Python, incluyendo Cadenas, Listas y Tuplas.

• in – Devuelve True si el elemento dado es una parte de la estructura.
• not in – Devuelve True si el elemento dado no forma parte de la estructura.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Los operadores de pertenencia son suficientes cuando todo lo que necesitamos es encontrar si existe una subcadena dentro de una cadena dada, o determinar si dos Cadenas, Listas o Tuplas se cruzan en términos de los objetos que contienen.

En la mayoría de los casos necesitamos la posición del elemento en la secuencia, además de determinar si existe o no; los operadores de pertenencia no cumplen este requisito.

Hay muchos algoritmos de búsqueda que no dependen de los operadores incorporados y que pueden utilizarse para buscar valores de forma más rápida y/o eficiente. Además, pueden dar más información, como la posición del elemento en la colección, en lugar de limitarse a determinar su existencia.

Búsqueda lineal

La búsqueda lineal es uno de los algoritmos de búsqueda más sencillos, y el más fácil de entender. Podemos pensar en él como una versión mejorada de nuestra propia implementación del operador in de Python.

El algoritmo consiste en iterar sobre un array y devolver el índice de la primera aparición de un elemento una vez encontrado:

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Así que si usamos la función para calcular:

>>> print(LinearSearch(, 2))

Al ejecutar el código, nos encontramos con:

1

Este es el índice de la primera aparición del elemento que estamos buscando – teniendo en cuenta que los índices de Python están basados en 0.

La complejidad temporal de la búsqueda lineal es O(n), lo que significa que el tiempo de ejecución aumenta con el número de elementos de nuestra lista de entrada lys.

La búsqueda lineal no se utiliza a menudo en la práctica, porque la misma eficiencia se puede lograr mediante el uso de métodos incorporados o los operadores existentes, y no es tan rápido o eficiente como otros algoritmos de búsqueda.

La búsqueda lineal es una buena opción para cuando necesitamos encontrar la primera aparición de un elemento en una colección no ordenada porque, a diferencia de la mayoría de los demás algoritmos de búsqueda, no requiere que una colección esté ordenada antes de comenzar la búsqueda.

Búsqueda binaria

La búsqueda binaria sigue una metodología de divide y vencerás. Es más rápida que la búsqueda lineal pero requiere que la matriz esté ordenada antes de ejecutar el algoritmo.

Suponiendo que buscamos un valor val en una matriz ordenada, el algoritmo compara val con el valor del elemento del medio de la matriz, que llamaremos mid.

• Si mid es el elemento que buscamos (el mejor caso), devolvemos su índice.
• Si no, identificamos en qué lado de mid es más probable que esté val en función de si val es menor o mayor que mid, y descartamos el otro lado del array.
• Luego seguimos recursivamente o iterativamente los mismos pasos, eligiendo un nuevo valor para mid, comparándolo con val y descartando la mitad de las posibles coincidencias en cada iteración del algoritmo.

El algoritmo de búsqueda binaria puede escribirse tanto recursivamente como iterativamente. La recursión es generalmente más lenta en Python porque requiere la asignación de nuevos marcos de pila.

Como un buen algoritmo de búsqueda debe ser lo más rápido y preciso posible, consideremos la implementación iterativa de la búsqueda binaria:

Si utilizamos la función para calcular:

>>> BinarySearch(, 20)

Obtenemos el resultado:

1

Que es el índice del valor que estamos buscando.

La acción que el algoritmo realiza a continuación en cada iteración es una de varias posibilidades:

• Devolver el índice del elemento actual
• Buscar por la mitad izquierda del array
• Buscar por la mitad derecha del array

Sólo podemos elegir una posibilidad por iteración, y nuestro conjunto de posibles coincidencias se divide por dos en cada iteración. Esto hace que la complejidad temporal de la búsqueda binaria sea O(log n).

Un inconveniente de la búsqueda binaria es que si hay múltiples apariciones de un elemento en la matriz, no devuelve el índice del primer elemento, sino el índice del elemento más cercano al medio:

>>> print(BinarySearch(, 4))

Ejecutando este trozo de código se obtendrá el índice del elemento del medio:

1

En comparación, realizando una búsqueda lineal en el mismo array se obtendría:

0

Que es el índice del primer elemento. Sin embargo, no podemos decir categóricamente que la búsqueda binaria no funcione si un array contiene el mismo elemento dos veces – puede funcionar igual que la búsqueda lineal y devolver la primera ocurrencia del elemento en algunos casos.

Si realizamos la búsqueda binaria en el array por ejemplo, y buscamos el 4, obtendríamos 3 como resultado.

La búsqueda binaria es bastante utilizada en la práctica porque es eficiente y rápida en comparación con la búsqueda lineal. Sin embargo, tiene algunos defectos, como su dependencia del operador //. Hay muchos otros algoritmos de búsqueda de dividir y conquistar que se derivan de la búsqueda binaria, vamos a examinar algunos de ellos a continuación.

Búsqueda por saltos

La búsqueda por saltos es similar a la búsqueda binaria en el sentido de que funciona en una matriz ordenada, y utiliza un enfoque similar de dividir y conquistar para buscar a través de ella.

Puede clasificarse como una mejora del algoritmo de búsqueda lineal, ya que depende de la búsqueda lineal para realizar la comparación real cuando se busca un valor.

Dado un array ordenado, en lugar de buscar a través de los elementos del array de forma incremental, buscamos en saltos. Así que en nuestra lista de entrada lys, si tenemos un tamaño de salto de salto nuestro algoritmo considerará los elementos en el orden lys, lys, lys, lys y así sucesivamente.

Con cada salto, almacenamos el valor anterior que miramos y su índice. Cuando encontramos un conjunto de valores donde lys<elemento<lys, realizamos una búsqueda lineal con lys como elemento más a la izquierda y lys como elemento más a la derecha de nuestro conjunto de búsqueda:

Dado que se trata de un algoritmo complejo, consideremos el cálculo paso a paso de la búsqueda de saltos con esta entrada:

>>> print(JumpSearch(, 5))

• La búsqueda de saltos determinaría primero el tamaño del salto calculando math.sqrt(len(lys)). Como tenemos 9 elementos, el tamaño del salto sería √9 = 3.
• A continuación, calculamos el valor de la variable right, que es el mínimo de la longitud del array menos 1, o el valor de left+jump, que en nuestro caso sería 0+3= 3. Como 3 es menor que 8 utilizamos 3 como valor de right.
• Ahora comprobamos si nuestro elemento de búsqueda, 5, está entre lys y lys. Como el 5 no está entre el 1 y el 4, seguimos adelante.
• A continuación, volvemos a hacer los cálculos y comprobamos si nuestro elemento de búsqueda está entre lys y lys, donde el 6 es 3+salto. Como 5 está entre 4 y 7, hacemos una búsqueda lineal en los elementos entre lys y lys y devolvemos el índice de nuestro elemento como:

4

La complejidad temporal de la búsqueda por saltos es O(√n), donde √n es el tamaño del salto, y n es la longitud de la lista, lo que sitúa a la búsqueda por saltos entre los algoritmos de búsqueda lineal y búsqueda binaria en términos de eficiencia.

La ventaja más importante de la búsqueda por saltos en comparación con la búsqueda binaria es que no depende del operador de división (/).

En la mayoría de las CPU, el uso del operador de división es costoso en comparación con otras operaciones aritméticas básicas (suma, resta y multiplicación), porque la implementación del algoritmo de división es iterativa.

El coste por sí mismo es muy pequeño, pero cuando el número de elementos a buscar es muy grande, y el número de operaciones de división que necesitamos realizar aumenta, el coste puede aumentar. Por lo tanto, la búsqueda por salto es mejor que la búsqueda binaria cuando hay un gran número de elementos en un sistema en el que incluso un pequeño aumento de la velocidad es importante.

Para hacer que la búsqueda por salto sea más rápida, podríamos utilizar la búsqueda binaria u otra búsqueda por salto interna para buscar a través de los bloques, en lugar de confiar en la búsqueda lineal, que es mucho más lenta.

Búsqueda Fibonacci

La búsqueda Fibonacci es otro algoritmo de división y conquista que tiene similitudes con la búsqueda binaria y la búsqueda por salto. Recibe su nombre porque utiliza los números de Fibonacci para calcular el tamaño del bloque o el rango de búsqueda en cada paso.

Los números de Fibonacci empiezan por cero y siguen el patrón 0, 1, 1, 2, 3, 5, 8, 13, 21… donde cada elemento es la suma de los dos números que le preceden inmediatamente.

El algoritmo trabaja con tres números de Fibonacci a la vez. Llamemos a los tres números fibM, fibM_minus_1 y fibM_minus_2 donde fibM_minus_1 y fibM_minus_2 son los dos números inmediatamente anteriores a fibM en la secuencia:

fibM = fibM_minus_1 + fibM_minus_2

Inicializamos los valores a 0,1 y 1 o los tres primeros números de la secuencia de Fibonacci para evitar obtener un error de índice en el caso de que nuestro array de búsqueda lys contenga un número muy pequeño de elementos.

Entonces elegimos el número más pequeño de la secuencia de Fibonacci que sea mayor o igual que el número de elementos de nuestra matriz de búsqueda lys, como el valor de fibM, y los dos números de Fibonacci inmediatamente anteriores como los valores de fibM_minus_1 y fibM_minus_2. Mientras el array tenga elementos restantes y el valor de fibM sea mayor que uno, hacemos:

• Comparar val con el valor del bloque en el rango hasta fibM_minus_2, y devolver el índice del elemento si coincide.
• Si el valor es mayor que el elemento que estamos mirando actualmente, movemos los valores de fibM, fibM_minus_1 y fibM_minus_2 dos pasos hacia abajo en la secuencia de Fibonacci, y restablecemos el índice al índice del elemento.
• Si el valor es menor que el elemento que estamos mirando actualmente, movemos los valores de fibM, fibM_minus_1 y fibM_minus_2 un paso hacia abajo en la secuencia de Fibonacci.

Veamos la implementación en Python de este algoritmo:

Si utilizamos la función FibonacciSearch para calcular:

>>> print(FibonacciSearch(, 6))

Veamos el proceso paso a paso de esta búsqueda:

• Determinar el menor número de Fibonacci mayor o igual a la longitud de la lista como fibM; en este caso, el menor número de Fibonacci que cumple nuestros requisitos es el 13.
• Los valores se asignarían como:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• A continuación, comprobamos el elemento lys donde 4 es el mínimo de -1+5 . Como el valor de lys es 5, que es menor que el valor que buscamos, movemos los números de Fibonacci un paso hacia abajo en la secuencia, haciendo los valores:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• A continuación, comprobamos el elemento lys donde 7 es el mínimo de 4+3. Como el valor de lys es 8, que es mayor que el valor que buscamos, movemos los números de Fibonacci dos pasos hacia abajo en la secuencia.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• Ahora comprobamos el elemento lys donde 5 es el mínimo de 4+1 . El valor de lys es 6, que es el valor que estamos buscando!

El resultado, como era de esperar es:

5

La complejidad temporal de la búsqueda Fibonacci es O(log n); la misma que la búsqueda binaria. Esto significa que el algoritmo es más rápido que la búsqueda lineal y la búsqueda por saltos en la mayoría de los casos.

La búsqueda de Fibonacci se puede utilizar cuando tenemos un número muy grande de elementos en los que buscar, y queremos reducir la ineficiencia asociada al uso de un algoritmo que depende del operador de división.

Una ventaja adicional de usar la búsqueda Fibonacci es que puede acomodar matrices de entrada que son demasiado grandes para ser mantenidas en la caché de la CPU o en la RAM, porque busca a través de elementos en tamaños de paso crecientes, y no en un tamaño fijo.

Búsqueda exponencial

La búsqueda exponencial es otro algoritmo de búsqueda que puede ser implementado de manera bastante simple en Python, en comparación con la búsqueda de salto y la búsqueda Fibonacci que son ambas un poco complejas. También se le conoce con los nombres de búsqueda al galope, búsqueda al doble y búsqueda de Struzik.

La búsqueda exponencial depende de la búsqueda binaria para realizar la comparación final de valores. El algoritmo funciona de la siguiente manera:

• Determinando el rango en el que es probable que esté el elemento que buscamos
• Utilizando la búsqueda binaria del rango para encontrar el índice exacto del elemento

La implementación en Python del algoritmo de búsqueda exponencial es:

Si utilizamos la función para encontrar el valor de:

>>> print(ExponentialSearch(,3))

El algoritmo funciona de la siguiente manera:

• Comprobando si el primer elemento de la lista coincide con el valor que buscamos – ya que lys es 1 y buscamos 3, ponemos el índice a 1 y seguimos adelante.
• Recorriendo todos los elementos de la lista, y mientras el elemento en la posición del índice sea menor o igual a nuestro valor, incrementando exponencialmente el valor de index en múltiplos de dos:
  • índice = 1, lys es 2, que es menor que 3, por lo que el índice se multiplica por 2 y se establece en 2.
  • índice = 2, lyses 3, que es igual a 3, por lo que el índice se multiplica por 2 y se establece en 4.
  • índice = 4, lyses 5, que es mayor que 3; el bucle se rompe en este punto.
• A continuación, realiza una búsqueda binaria cortando la lista; arr. En Python, esto significa que la sublista contendrá todos los elementos hasta el 4º elemento, por lo que en realidad estamos llamando a:

>>> BinarySearch(, 3)

que devolvería:

2

que es el índice del elemento que estamos buscando tanto en la lista original, como en la lista troceada que pasamos al algoritmo de búsqueda binaria.

La búsqueda exponencial se ejecuta en tiempo O(log i), donde i es el índice del elemento que estamos buscando. En su peor caso, la complejidad temporal es O(log n), cuando el último elemento es el que estamos buscando (siendo n la longitud del array).

La búsqueda exponencial funciona mejor que la búsqueda binaria cuando el elemento que buscamos está más cerca del principio del array. En la práctica, utilizamos la búsqueda exponencial porque es uno de los algoritmos de búsqueda más eficientes para matrices no limitadas o infinitas.

Búsqueda por interpolación

La búsqueda por interpolación es otro algoritmo de divide y vencerás, similar a la búsqueda binaria. A diferencia de la búsqueda binaria, no siempre comienza a buscar en el centro. La búsqueda por interpolación calcula la posición probable del elemento que estamos buscando mediante la fórmula:

index = low + )*(high-low) / (lys-lys)]

Donde las variables son:

• lys – nuestra matriz de entrada
• val – el elemento que estamos buscando
• index – el índice probable del elemento buscado. Esto se calcula para ser un valor más alto cuando val está más cerca en valor al elemento al final de la matriz (lys), y más bajo cuando val está más cerca en valor al elemento al principio de la matriz (lys)
• low – el índice inicial de la matriz
• high – el último índice de la matriz

El algoritmo busca calculando el valor de index:

• Si se encuentra una coincidencia (cuando lys == val), se devuelve el índice
• Si el valor de val es menor que lys, el valor para el índice se vuelve a calcular utilizando la fórmula de la submatriz izquierda
• Si el valor de val es mayor que lys, el valor del índice se recalcula usando la fórmula de la submatriz derecha

Vamos a implementar la búsqueda por interpolación usando Python:

Si utilizamos la función para calcular:

>>> print(InterpolationSearch(, 6))

Nuestros valores iniciales serían:

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Como lys es 6, que es el valor que buscamos, dejamos de ejecutar y devolvemos el resultado:

5

Si tenemos un gran número de elementos, y nuestro índice no se puede calcular en una iteración, seguimos recalculando valores para el índice después de ajustar los valores de alto y bajo en nuestra fórmula.

La complejidad temporal de la búsqueda de interpolación es O(log log n) cuando los valores están distribuidos uniformemente. Si los valores no están distribuidos uniformemente, la complejidad de tiempo en el peor de los casos es O(n), igual que la búsqueda lineal.

La búsqueda por interpolación funciona mejor en matrices ordenadas y distribuidas uniformemente. Mientras que la búsqueda binaria comienza en el centro y siempre se divide en dos, la búsqueda por interpolación calcula la posición probable del elemento y comprueba el índice, por lo que es más probable encontrar el elemento en un menor número de iteraciones.

¿Por qué usar Python para buscar?

Python es muy legible y eficiente en comparación con los lenguajes de programación más antiguos como Java, Fortran, C, C++, etc. Una ventaja clave de usar Python para implementar algoritmos de búsqueda es que no hay que preocuparse por el casting o la tipificación explícita.

En Python, la mayoría de los algoritmos de búsqueda que hemos discutido funcionarán igual de bien si buscamos una Cadena. Tenga en cuenta que tenemos que hacer cambios en el código para los algoritmos que utilizan el elemento de búsqueda para los cálculos numéricos, como el algoritmo de búsqueda de interpolación.

Python es también un buen lugar para empezar si desea comparar el rendimiento de diferentes algoritmos de búsqueda para su conjunto de datos; la construcción de un prototipo en Python es más fácil y más rápido porque se puede hacer más con menos líneas de código.

Para comparar el rendimiento de nuestros algoritmos de búsqueda implementados contra un conjunto de datos, podemos utilizar la biblioteca de tiempo en Python:

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Conclusión

Hay muchas formas posibles de buscar un elemento dentro de una colección. En este artículo, hemos intentado discutir algunos algoritmos de búsqueda y sus implementaciones en Python.

La elección del algoritmo a utilizar se basa en los datos que tienes que buscar; tu array de entrada, que hemos llamado lys en todas nuestras implementaciones.

• Si quieres buscar en un array sin ordenar o encontrar la primera aparición de una variable de búsqueda, la mejor opción es la búsqueda lineal.
• Si quieres buscar en un array ordenado, hay muchas opciones de las cuales el método más sencillo y rápido es la búsqueda binaria.
• Si tienes un array ordenado en el que quieres buscar sin usar el operador de división, puedes usar la búsqueda por saltos o la búsqueda de Fibonacci.
• Si sabes que el elemento que buscas probablemente esté más cerca del principio del array, puedes usar la búsqueda exponencial.
• Si tu matriz ordenada también está distribuida uniformemente, el algoritmo de búsqueda más rápido y eficiente sería la búsqueda por interpolación.

Si no estás seguro de qué algoritmo utilizar con una matriz ordenada, simplemente prueba cada uno de ellos junto con la biblioteca de tiempo de Python y elige el que mejor funcione con tu conjunto de datos.