Algoritmos de Búsqueda en Python

imagen / Adam Wilson
  
11 de Septiembre de 2017   0  

Introducción:
Problema de la Búsqueda: Dada una lista xn y un valor x devolver el índice de x en xn si x está en xn, y −1 si x no está en xn.

El problema que acabo de presentarte, es uno de los problemas más clásicos de la computación, "El Problema de la Búsqueda", nuestro objetivo de hoy, será escribir 3 algoritmos diferentes que nos ayuden a resolver este problema, si te interesa sigue leyendo.

 

Algoritmos de Búsqueda:
-Con mucha frecuencia los programadores trabajamos con grandes cantidades de datos almacenados en una lista o en cualquier estructura de datos, y por ello será necesario determinar si una lista contiene un valor que coincida con un cierto valor clave, para saber si un valor se encuentra dentro de una determinada lista o vector (depende de ti como quieras llamarlo), se hace uso de los Algoritmos de Búsqueda, los cuales nos permiten encontrar un determinada valor dentro de una estructura de datos: por ejemplo, ubicar el registro correspondiente a cierta persona en una base de datos.
Para cumplir con el objetivo de hoy que es resolver el Problema de Búsqueda, usaremos  dos técnicas de búsqueda: búsqueda lineal o secuencial,la técnica más sencilla, y búsqueda binaria o dicotómica, la técnica más eficiente.

 

1. Búsqueda Lineal:

-Este tipo de algoritmo, como su nombre indica, busca desde el primer dato hasta el último, uno a uno comparando sucesivamente todos los datos en memoria hasta localizar el dato que queramos localizar. Este algoritmo puede usarse en cualquier situación, pero se recomienda usarlo solo en listas que no estén ordenadas, ya que para las que lo estén podremos usar el siguiente algoritmo, que es mucho más eficiente.

Solución del Problema con la Búsqueda Lineal:

Problema de la Búsqueda: Dada una lista xn y un valor x devolver el índice de x en xn si x está en xn, y −1 si x no está en xn.

Diseñamos una solución: Podemos comparar uno a uno los elementos de la lista con el valor
de x, y retornar el valor de la posición donde lo encontramos en caso de encontrarlo.
Si llegamos al final de la lista sin haber salido antes de la función es porque el valor de x no
está en la lista, y en ese caso retornamos −1.
En esta solución necesitamos una variable i que cuente en cada momento en qué posición
de la lista estamos parados. Esta variable se inicializa en 0 antes de entrar en el ciclo y se
incrementa en 1 en cada paso.

Codigo del Algoritmo:


""" Búsqueda lineal.
 Si x está en lista devuelve su posición en lista, de lo
 contrario devuelve -1.
 """
#Función del Algoritmo: se recorren uno a uno los elementos de la lista 
#y se los compara con el valor x buscado.
def busqueda_lineal(lista, x):
 	i = 0 # i tiene la posición actual en la lista, comienza en 0
	#El ciclo recorre todos los elementos de la lista
	for z in lista:
		# estamos en la posicion i, z contiene el valor de lista[i]
		#Si z es igual a x, devuelve el valor de i
		if z == x:
			return i
		i = i+1
	#si salió del ciclo sin haber encontrado el valor, devuelve -1
	return -1

Resultado:
>>> busqueda_lineal([1, 4, 54, 3, 0, 34, 23, 12], 2)
-1
>>> busqueda_lineal([1, 4, 54, 3, 0, 34, 23, 12], 23)
6
>>> busqueda_lineal([1, 4, 54, 3, 0, 34, 23, 12], 4)
1


2. Búsqueda Binaria:

-En este caso, este tipo de búsqueda es usado en listas que estén previamente ordenadas, ya que su método de búsqueda es la de dividir los datos en dos grupos, eligiendo el grupo en el cual debería estar el dato buscado (supone que está ordenado alfabéticamente o numericamente), volviendo a aplicar la división, y así sucesivamente hasta verificar si existe o no existe el dato buscado.

Solución del Problema con la Búsqueda Binaria:

Problema de la Búsqueda: Dada una lista xn y un valor x devolver el índice de x en xn si x está en xn, y −1 si x no está en xn.

Procedmiento: Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del vector (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del vector que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del vector que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el vector.

Codigo del Algoritmo:

"""
Búsqueda Binaria.
"""
#Este es el vector que el algoritmo usara para buscar cualquier dato
vector = [3, 5, 8, 9, 10, 22, 45, 500, 900, 4253]
#La variable puntero sera el inicio del vector, que es 0
puntero = 0
#vectorLen contiene la longitud del vector
vectorLen = len(vector)
#La varieable encontrado cambiara su valor, y asi el algoritmo sabre que hacer luego
encontrado = False

#Le pedimos al usuario una entrada de un entero
numero = int(input("Ingresar el dato que desea buscar: "))

#Creamos un bucle que no se detenga hasta que encontrado sea diferente de False
#Y que puntero sea menor o igual que vectorLen
while not(encontrado) and puntero <= vectorLen:
	#Creamos la variable mitad
	mitad = int((puntero+vectorLen) / 2)
	#Si numero es igual que el indice mitad en vector
	if numero == vector[mitad]:
		#Encontado sera igual a True
		encontrado = True
	#De lo contrario, si el indice mitad en vector es menor que numero
	elif numero < vector[mitad]:
		#vectorLen sera igual que mitad - 1
		vectorLen = mitad - 1
	#De lo contrario
	else:
		#Puntero sera igual que mitad + 1
		puntero = mitad + 1
#Si encontrado es True
if(encontrado):
	#MOstramos un mensaje con la posicion del Dato en el vector
	print("El dato se encuentra en la posicion ", str(mitad+1))
	#Mostramos el vector ordenado
	print(vector)
#De lo contrario
else:
	#Mostramos un mensaje avisandole al usuario que el dato ingresado no se encuentra dentro del vector
	print("El dato no se encontro")

Resultado:
Ingresar el dato que desea buscar: 8
El dato se encuentra en la posicion  3
[3, 5, 8, 9, 10, 22, 45, 500, 900, 4253] 

 

Finalización:

¡Excelente! hemos cumplido con nuestro objetivo, resolvimos el problema de la búsqueda con 2 algoritmos diferentes, como pueden ver, los algoritmos de búsqueda aparte de ser muy interesantes son de mucha ayuda, espero que te haya sido de utilidad, ya sea para resolver problemas o para reforzar tus conocimientos.



Luis Alejandro

Temas relacionados