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 2 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.
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.
Código 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 listafor z in lista:
#Si z es igual a x, devuelve el valor de iif z == x:
return i
i = i+1
#si salió del ciclo sin haber encontrado el valor, devuelve -1return -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.
Procedimiento: 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.
Código 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
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 vectorLenwhilenot(encontrado) and puntero <= vectorLen:
#Creamos la variable mitad
mitad = int((puntero+vectorLen) / 2)
#Si numero es igual que el indice mitad en vectorif numero == vector[mitad]:
#Encontado sera igual a True
encontrado = True
elif numero < vector[mitad]:
#vectorLen sera igual que mitad - 1
vectorLen = mitad - 1
#De lo contrarioelse:
#Puntero sera igual que mitad + 1
puntero = mitad + 1
#Si encontrado es Trueif(encontrado):
#Mostramos un mensaje con la posicion del Dato en el vectorprint("El dato se encuentra en la posición ", str(mitad+1))
#Mostramos el vector ordenadoprint(vector)
#De lo contrarioelse:
#Mostramos un mensaje print("El dato no se encontró")
Resultado:
Ingresar el dato que desea buscar: 8
El dato se encuentra en la posición 3
[3, 5, 8, 9, 10, 22, 45, 500, 900, 4253]
¡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.
Comparte tu experiencia con nosotros dejando un buen comentario. Mi nombre es Luis, y fue un placer compartir mis conocimientos con ustedes :D.
alexander_03019@outlook.com dice: 
alexander_03019@outlook.com 
excelente comosiempre !!!Gracias