Implementaciones de algoritmos de búsqueda en Python

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 pensamos que podría colocarse. 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. Veremos algunos algoritmos que siguen diferentes patrones de búsqueda en este artículo.

Existen 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. Y el resto de los algoritmos será muy fácil de aprender.

La búsqueda se refiere a buscando un elemento en la matriz en este articulo.

Vamos a verlos uno por uno.

Linear Search

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

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

Si observa atentamente el patrón de búsqueda, encontrará que el tiempo necesario para la ejecución del programa será O (n) en el capítulo respecto a la peor de los casos. Tenemos que considerar la complejidad temporal del peor caso 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, conoce bien el algoritmo de búsqueda lineal. Es hora de ensuciarnos las manos con algún código. Veamos primero los pasos para implementar la búsqueda lineal. Entonces intentas codificarlo. No se preocupe incluso si no puede; Le 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).
• Escribe una función llamada elemento_búsqueda, que acepta tres argumentos, matriz, longitud de la matriz y elemento a buscar.
• elemento_búsqueda (arr, n, elemento):
  • Itere sobre la matriz dada.
    • Compruebe si el elemento actual es igual al elemento requerido.
    • Si es así, regresa Verdadero.
  • Después de completar el ciclo, si la ejecución todavía está en la función, entonces el elemento no está presente en la matriz. Por lo tanto volver Falso.
• Imprime el mensaje según el valor de retorno de la función elemento_búsqueda.

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? Yo espero que sí. Si completó, verifique con el siguiente código.

Si no lo completó, no se preocupe; vea el código a continuación 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.

Binary Search

EL algoritmo de búsqueda binaria siempre comprueba el elemento medio de la matriz. Este algoritmo busca el elemento en un matriz ordenada.

EL algoritmo de búsqueda binaria itera sobre la matriz y verifica el elemento del medio, si lo encuentra, luego detiene el programa. De lo contrario, si el elemento intermedio es menor que el elemento requerido, omite la parte izquierda de la matriz del elemento intermedio de la búsqueda. De lo contrario, si el elemento intermedio es mayor que el elemento requerido, omite la parte derecha de la matriz del elemento intermedio de la búsqueda.

En cada iteración, el algoritmo de búsqueda binaria reduce el área para buscar el elemento. Por 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 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)
• Escribe una función llamada elemento_búsqueda, que acepta tres argumentos, matriz ordenada, longitud de la matriz y elemento a buscar.
• search_element (sorted_arr, n, elemento):
  • Inicializar la variable de índice i para la iteración de matrices.
  • A continuación, inicialice dos variables para mantener el área de búsqueda de la matriz. Aquí, los llamamos como comienzo y final como indican índices.
  • Iterar hasta que i es menor que la longitud de la matriz.
    • Calcule el índice medio del área de búsqueda usando el comienzo y final valores. Eso será (inicio + fin) // 2.
    • Compruebe si el elemento indexado del medio del área de búsqueda es igual al elemento requerido o no.
    • Si es así, regresa Verdadero.
    • De lo contrario, si el elemento indexado del medio es menor que el elemento requerido, mueva el comienzo índice del área de búsqueda para medio + 1.
    • De lo contrario, si el elemento indexado del medio es mayor que el elemento requerido, mueva el final índice del área de búsqueda para medio - 1.
    • Incrementar el índice de la matriz i.
  • Después de completar el ciclo, si la ejecución todavía está en la función, entonces el elemento no está presente en la matriz. Por lo tanto volver Falso.
• Imprime el mensaje según el valor de retorno de la función elemento_búsqueda.

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

...

¿Recibiste el código?

Sí, compárelo con el siguiente código. No, no se preocupe; Comprenda 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 que el algoritmo de búsqueda binaria no sea 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 software de búsqueda autohospedado.

Codificación feliz 🙂 🧑‍💻