Me preguntaba como poder hacer una búsqueda dentro de un arreglo, o lista, que sea eficiente. He investigado y leído sobre algoritmos de búsqueda, y me encontré con el término de búsqueda binaria. Estaría bien recebir ayuda.
¡Muchas gracias!
Stack Overflow en español es un sitio de preguntas y respuestas para programadores y profesionales de la informática. Solo te toma un minuto registrarte.
Regístrate para unirte a esta comunidadEl algoritmo de Búsqueda Binaria solo se puede aplicar a arreglos, o listas, que estén estrictamente ordenadas, da igual de menor a mayor, o de mayor a menor, pero estrictamente deben estar ordenadas.
Para poder crear este algoritmo en python, deberemos crear una lista por ejemplo:
fList = [1,2,3,4,5,6,7,8,9]
Y una variable que sea el número a buscar, ya puede ser pidiéndolo por consola o escribiéndolo previamente, por ejemplo:
x = int(input("Numero del arreglo a elegir: "))
or
x = 2
Después de haber establecido el número a buscar y la lista donde lo buscaremos, empezaremos a trabajar con el algoritmo de búsqueda.
Cosas a entender antes de trabajar con el algoritmo de Búsqueda Binaria:
Deberemos establecer tanto el numero final de nuestra lista, que sería el último indice de nuestra lista, como el primer numero de nuestra lista, que siempre es 0.
Habrá que establecer un numero entero que sea el que esté siempre en la mitad del rango de búsqueda.
El algoritmo basa su búsqueda en acortar el índice de nuestra lista hasta encontrar el número especificado, no es un algoritmo de comparación de datos, cual procesamiento es cuadrático.
Después de conocer esto, procedemos con el código, que sería éste:
def main():
lista = [1,8,6,4,8,5,12,455,78,41,50,90,1100,548,523,658,987,4125,32145,248652,45524,822445,11,5,16,5465,4,465,42321,65,45,153,54,9,5436,515645,65,6]
x = 65
binarySearch(lista, x)
def binarySearch(lista, x):
left = 0
right = len(lista) - 1
mid = 0
lista.sort()
while(left <= right):
mid = (left+right) // 2
if lista[mid] < x:
left = mid + 1
print("Current left is: {}".format(left))
print("Current right is: {}".format(right))
if lista[mid] > x:
right = mid - 1
print("Current left is: {}".format(left))
print("Current right is: {}".format(right))
if lista[mid] == x:
print("EL numero está en la posicion: {}".format(mid))
break
if x not in lista:
print("El numero no esta")
break
if __name__ == "__main__":
main()
Como podemos ver, el numero del medio deberá ser siempre la mitad rango de nuestros índices izquierda y derecha, que se hace con la simple operación de la suma del índice izquierdo e índice derecho dividiédolo entre dos como un entero (Para dividir y que nuestro resultado sea entero, se usa //)
Funcionamiento del algoritmo escrito:
3 in lista
te retornaTrue
si el valor 3 aparece en la lista. O bienlista.index(3)
te devuelve el índice en que el 3 aparece. Internamente esas operaciones están implementadas de forma eficiente, aunque van a requerir más tiempo cuanto mayor sea la lista (complejidad O(N)). Para tener tiempos independientes del tamaño deberías usar conjuntos o diccionarios.