Implementación de algoritmos de búsqueda en Python

Implementar la búsqueda es siempre un reto, pero no imposible

En la vida real, buscaremos sin seguir ningún patrón. Simplemente vamos a los lugares en los que creemos que puede estar. No seguimos ningún patrón en la mayoría de los casos

¿Ocurre lo mismo en el mundo de la programación?

No! tiene que haber algún patrón para buscar cosas en los programas. Vamos a ver algunos algoritmos que siguen diferentes patrones para buscar en este artículo

Hay múltiples algoritmos que podemos encontrar en el mundo de la programación. Vamos a discutir los algoritmos más importantes y más utilizados en este artículo. El resto de algoritmos le resultará muy fácil de aprender

Buscar se refiere a buscar un elemento en el array en este artículo

Veámoslos uno a uno

Búsqueda lineal

El nombre sugiere que el algoritmo de búsqueda lineal sigue elpatrón lineal para buscar los elementos en un array. El algoritmo empieza a buscar el elemento desde el principio del array y se mueve hacia el final hasta que encuentra el elemento. Detiene la ejecución del programa cuando encuentra el elemento deseado

Vamos a ilustrar los algoritmos de búsqueda lineal con algunas ilustraciones interesantes para una mejor comprensión del algoritmo

Si observa detenidamente el patrón de búsqueda, comprobará que el tiempo de ejecución del programa será O(n) en el peor de los casos. Tenemos que considerar la complejidad temporal en el peor de los casos de los algoritmos a analizar. Por lo tanto, la complejidad temporal del algoritmo es O (n)

Veamos la implementación del algoritmo de búsqueda lineal

Implementación de la búsqueda lineal

Ahora ya entiende bien el algoritmo de búsqueda lineal. Es hora de ensuciarnos las manos con algo de código. Veamos primero los pasos para implementar la búsqueda lineal. A continuación, intente codificarla. No se preocupe aunque no pueda; después le proporcionaré el código

Veamos los pasos para implementar el algoritmo de búsqueda lineal

Inicialice una matriz de elementos (sus números de la suerte).
Escriba una función llamada buscar_elemento , que acepta tres argumentos, array, longitud del array y elemento a buscar.
buscar_elemento(arr, n, elemento)
- Iterar sobre la matriz dada
  - Comprueba si el elemento actual es igual al elemento buscado.
  - En caso afirmativo, devuelva Verdadero.
- Después de completar el bucle, si la ejecución sigue en la función, entonces el elemento no está presente en el array. Por lo tanto devuelve Falso.
Imprima el mensaje basado en el valor de retorno de la función buscar_elemento.

Por último, escriba el código con la ayuda de los pasos anteriores para implementar el algoritmo de búsqueda lineal

¿Ha completado la implementación del algoritmo de búsqueda lineal? Espero que sí. Si la ha completado, compruébelo con el siguiente código

Si no lo completó, no se preocupe,; vea el siguiente código y aprenda cómo lo implementamos. Lo conseguirá sin mucho esfuerzo

## función de búsqueda
def buscar_elemento(arr, n, elemento):

## iterando a través del array
for i in range(n):

## comprobando el elemento actual con el elemento requerido
if arr[i] == elemento:
## devolviendo True en caso de coincidencia
return True

## el elemento no se encuentra de ahí que la ejecución venga aquí
return False


if __name__ == '__main__':
	## inicializar la matriz, la longitud y el elemento a buscar
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
elemento_a_buscar = 6
# elemento_a_buscar = 11

if buscar_elemento(arr, n, elemento_a_buscar):
		print(elemento_a_buscar, "se encuentra")
else:
print(elemento_a_buscar, "no se encuentra")

Primero, ejecútelo con un elemento que esté presente en la matriz. Y a continuación, ejecútelo con un elemento que no esté presente en la matriz

La complejidad temporal del algoritmo de búsqueda lineal es O(n)

¿Podemos reducirla un poco más con diferentes patrones?

Sí, podemos. Veámoslo

Búsqueda binaria

El algoritmo de búsqueda binaria comprueba siempre el elemento central de la matriz. Este algoritmo busca el elemento en una matriz ordenada

El algoritmo de búsqueda binaria itera sobre la matriz y comprueba el elemento del medio, si lo encuentra, entonces detiene el programa. Si el elemento medio es menor que el elemento requerido, entonces omite la parte izquierda de la matriz del elemento medio de la búsqueda. Si el elemento central es mayor que el elemento requerido, omite la parte derecha de la matriz del elemento central de la búsqueda

En cada iteración, el algoritmo de búsqueda binaria reduce el área de búsqueda del elemento. Así, el número de comprobaciones es menor que el número de comprobaciones realizadas en el algoritmo de búsqueda lineal

Las ilustraciones nos ayudan a comprender mejor el algoritmo de búsqueda binaria. Vamos a verlas

La complejidad temporal del algoritmo de búsqueda binaria es O(log n). En cada iteración, la longitud del área de búsqueda se reduce a la mitad. Se reduce exponencialmente

Implementación de la búsqueda binaria

Primero veremos los pasos para implementar el algoritmo de búsqueda binaria y después el código. Veamos los pasos para completar la implementación del algoritmo de búsqueda binaria

Inicialice la matriz con elementos (sus números de la suerte)
Escriba una función llamada buscar_elemento , que acepte tres argumentos, matriz ordenada, longitud de la matriz y elemento a buscar.
buscar_elemento(matriz_ordenada, n, elemento)
- Inicialice la variable de índice i para la iteración del array.
- A continuación, inicialice dos variables para mantener el área de búsqueda del array. Aquí las llamamos inicio y aleta porque indican índices.
- Itere hasta que i mar menor que la longitud del array
  - Calcule el índice medio del área de búsqueda utilizando los valores de inicio y aleta . Será (inicio fin) // 2.
  - Compruebe si el elemento indexado del medio de la zona de búsqueda es igual al elemento requerido o no.
  - En caso afirmativo, devolverá Verdadero.
  - De lo contrario, si el elemento indexado del medio es menor que el elemento requerido, entonces mueva el índice de inicio del área de búsqueda al medio 1.
  - Else si el elemento indexado medio es mayor que el elemento requerido, entonces mueva el índice final del área de búsqueda a medio – 1.
  - Incremente el índice de la matriz i.
- Después de completar el bucle, si la ejecución sigue en la función, entonces el elemento no está presente en el array. Por lo tanto devuelve Falso.
Imprima el mensaje basado en el valor de retorno de la función buscar_elemento.

Intente escribir el código de forma similar a la implementación del algoritmo de búsqueda lineal

¿Ha conseguido el código?

Sí, compárelo con el código siguiente. No, no se preocupe; entienda la implementación con el código de abajo

## función de búsqueda
def buscar_elemento(array_ordenado, n, elemento):

## índice del array para la iteración
i = 0

## variables para rastrear el área de búsqueda
## inicializándolas con los índices de inicio y fin
inicio = 0
fin = n - 1

## iterando sobre el array
while i < n:
		## obteniendo el índice del elemento medio
medio = (inicio fin) // 2

## comprobando el elemento medio con el elemento requerido
si sorted_arr<x>[medio]</x> == elemento:
## devolviendo True ya que el elemento está en la matriz
return True
elif sorted_arr<x>[medio]</x> < elemento:
			## moviendo el índice de inicio de la zona de búsqueda a la derecha
inicio = medio 1
si no:
## moviendo el índice de fin de la zona de búsqueda a la izquierda
fin = medio - 1
i = 1
return False


if __name__ == '__main__':
	## inicializar la matriz, la longitud y el elemento a buscar
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = 10
elemento_a_buscar = 9
# elemento_a_buscar = 11

if buscar_elemento(arr, n, elemento_a_buscar):
		print(elemento_a_buscar, "se encuentra")
else:
print(elemento_a_buscar, "no se encuentra")

Pruebe el código con diferentes casos en los que el elemento esté presente y no lo esté en algunos casos

Conclusión

El algoritmo de búsqueda binaria es mucho más eficiente que el algoritmo de búsqueda lineal. Necesitamos ordenar el array para el algoritmo de búsqueda binaria no es el caso en el algoritmo de búsqueda lineal. La ordenación requiere cierto tiempo. Pero, el uso de algoritmos eficientes para la ordenación formará una buena combinación con el algoritmo de búsqueda binaria

Ahora, tiene un buen conocimiento de los algoritmos más utilizados en Python

A continuación, descubra algunos de los programas de búsqueda autoalojados más populares

Feliz codificación 🙂 🧑‍💻