Implementaciones de algoritmos de búsqueda en Python

por

Implementar la búsqueda siempre es un desafío, pero no imposible.

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

¿Funciona 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 de búsqueda en este artículo.

Son múltiples los 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. Y el resto de los algoritmos será pan comido para que los aprendas.

Buscar se refiere a buscar un elemento en la matriz de este artículo.

Vamos a verlos uno por uno.

Búsqueda lineal

El nombre sugiere que el algoritmo de búsqueda lineal sigue el patrón lineal para buscar los elementos en una matriz. El algoritmo comienza a buscar el elemento desde el principio de la matriz y avanza hasta el final hasta que encuentra el elemento. Detiene la ejecución del programa cuando encuentra el elemento requerido.

Ilustremos los algoritmos de búsqueda lineal con algunas ilustraciones geniales para una mejor comprensión del algoritmo.

Si observa cuidadosamente el patrón de búsqueda, encontrará que el tiempo que tarda la ejecución del programa será O(n) en el peor de los casos. Tenemos que considerar la complejidad temporal del 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 búsqueda lineal

Ahora, tiene una buena comprensión del 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. Luego intentas codificarlo. No te preocupes incluso si no puedes; Te proporcionaré el código después.

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 acepte tres argumentos, matriz, longitud de la matriz y elemento a buscar.
  • buscar_elemento(arr, n, elemento):
    • Iterar sobre la matriz dada.
      • Compruebe si el elemento actual es igual al elemento requerido.
      • En caso afirmativo, devuelva True.
    • Después de completar el ciclo, si la ejecución aún está en la función, entonces el elemento no está presente en la matriz. Por lo tanto, devuelve Falso.
  • Imprime el mensaje basado en el valor de retorno de la función search_element.

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

¿Completaste la implementación del algoritmo de búsqueda lineal? Eso espero. Si completó, luego verifique con el siguiente código.

Si no lo completaste, no te preocupes; vea el siguiente código y aprenda cómo lo implementamos. Lo conseguirás sin mucho esfuerzo.

## searching function
def search_element(arr, n, element):

	## iterating through the array
	for i in range(n):

		## checking the current element with required element
		if arr[i] == element:
			## returning True on match
			return True

	## element is not found hence the execution comes here
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Primero, ejecute el programa con un elemento que esté presente en la matriz. Y luego, 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 reducirlo un poco más con diferentes patrones?

Sí, podemos. Vamos a verlo.

Búsqueda binaria

El algoritmo de búsqueda binaria siempre verifica 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 verifica el elemento central, si lo encuentra, luego detiene el programa. De lo contrario, si el elemento central es menor que el elemento requerido, entonces omite la parte izquierda de la matriz del elemento central de la búsqueda. De lo contrario, si el elemento del medio es mayor que el elemento requerido, entonces omite la parte derecha de la matriz del elemento del medio de la búsqueda.

En cada iteración, el algoritmo de búsqueda binaria reduce el área para buscar el elemento. Por lo tanto, 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 comprobarlos.

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 está reduciendo exponencialmente.

Implementación de búsqueda binaria

Primero veremos los pasos para implementar el algoritmo de búsqueda binaria y luego 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 elemento_búsqueda, que acepte tres argumentos, matriz ordenada, longitud de la matriz y elemento a buscar.
  • elemento_búsqueda(clasificado_arr, n, elemento):
    • Inicialice la variable de índice i para la iteración de matriz.
    • Luego, inicialice dos variables para mantener el área de búsqueda de la matriz. Aquí, los llamamos inicio y fin, ya que indican índices.
    • Iterar hasta que i sea menor que la longitud de la matriz.
      • Calcule el índice medio del área de búsqueda utilizando los valores inicial y final. Eso será (inicio + fin) // 2.
      • Compruebe si el elemento indexado medio del área de búsqueda es igual al elemento requerido o no.
      • En caso afirmativo, devuelva True.
      • De lo contrario, si el elemento indexado del medio es menor que el elemento requerido, mueva el índice de inicio del área de búsqueda al medio + 1.
      • De lo contrario, si el elemento indexado del medio es mayor que el elemento requerido, mueva el índice final del área de búsqueda al medio – 1.
      • Incrementa el índice de la matriz i.
    • Después de completar el ciclo, si la ejecución aún está en la función, entonces el elemento no está presente en la matriz. Por lo tanto, devuelve Falso.
  • Imprime el mensaje basado en el valor de retorno de la función search_element.

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

…

¿Conseguiste el código?

Sí, compárelo con el siguiente código. No, no te preocupes; entender la implementación con el siguiente código.

## searching function
def search_element(sorted_arr, n, element):

	## array index for iteration
	i = 0

	## variables to track the search area
	## initializing them with start and end indexes
	start = 0
	end = n - 1

	## iterating over the array
	while i < n:
		## getting the index of the middle element
		middle = (start + end) // 2

		## checking the middle element with required element
		if sorted_arr[middle] == element:
			## returning True since the element is in the array
			return True
		elif sorted_arr[middle] < element:
			## moving the start index of the search area to right
			start = middle + 1
		else:
			## moving the end index of the search area to left
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## initializing the array, length, and element to be searched
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "is found")
	else:
		print(element_to_be_searched, "is not found")

Pruebe el código con diferentes casos donde el elemento está presente y no presente 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 la matriz para el algoritmo de búsqueda binaria, no es el caso en el algoritmo de búsqueda lineal. La clasificación lleva algún tiempo. Pero el uso de algoritmos eficientes para clasificar 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 populares programas de búsqueda autohospedados.

Codificación feliz 🙂 🧑‍💻

No related posts.