Búsqueda binaria de Python
Una búsqueda binaria es una forma de encontrar un cierto elemento dentro de una lista. Imaginemos que tenemos una lista de diez mil elementos y necesitamos encontrar la posición de índice de una sola entrada. Podemos encontrar rápidamente la ubicación del índice de un elemento utilizando la técnica de búsqueda binaria. Existen otros algoritmos de búsqueda, pero el más ampliamente empleado es una búsqueda binaria. Ordene los objetos primero si aún no se han ordenado.
Los enfoques recursivos e iterativos del algoritmo de búsqueda binario se pueden utilizar para encontrar la posición del elemento. La estrategia recursiva se usa después del enfoque de división y conquistar. De esta manera, se realiza una función hasta que encuentre un elemento en la lista. Para descubrir la ubicación del índice de un elemento, la técnica iterativa repite repetidamente un conjunto de palabras. Este proceso se logra utilizando el bucle while. Debido a que no tenemos que buscar en cada índice de lista, la búsqueda binaria es más eficiente que la búsqueda lineal.
Comencemos con una comprensión básica de la búsqueda binaria.
Ejemplo 1:
Primero, utilizamos el enfoque iterativo para implementar una búsqueda binaria. Vamos a recorrer la lista, repitiendo una secuencia de declaraciones. Continuaremos buscando el valor central hasta que lo encontremos.
Esta es una implementación de Python del enfoque de función de búsqueda binaria iterativa. Si 'search_num' está presente en la lista dada, devuelve uno; de lo contrario, da -1. Construimos la función Binary Search () en este programa, que acepta dos argumentos: una lista para clasificar y un número para buscar. Hemos configurado dos variables para realizar un seguimiento de los valores más bajos y mayores de la lista. El bajo tiene un valor inicial de 0, el alto tiene un valor de len (list1) - 1, y el medio tiene un valor de 0. El bucle mientras se escribe con la restricción de que el más bajo es igual y es más pequeño que el más alto. El bucle mientras se iterará si el número aún no se ha encontrado. El punto medio se encuentra en el bucle while. Luego coincidimos con el valor del índice con el número que hemos estado buscando. Si el valor del índice medio es menor que el 'número de búsqueda', lo asignamos y elevamos el valor de índice medio por uno. El enfoque de la búsqueda cambia a la izquierda. Establezca el valor medio al máximo si es alto. Devuelve Mid si el 'Search_num' es igual al valor medio. Esto continuará hasta que los bajos y altos sean iguales y el bajo es más pequeño que el alto. Si llegamos al final de la función, sabemos que el elemento no está en la lista. A la función de invocación, devolvemos -1.
def binary_search (uno, search_num):bajo = 0
alto = len (uno) - 1
Mid = 0
mientras bajo <= high:
Mid = (alto + bajo) // 2
Si uno [Mid] search_num:
Alto = Mid - 1
demás:
regresar a medio
retorno -1
uno = [19, 23, 43, 56, 65, 71, 80]
Search_num = 43
output = binary_search (uno, search_num)
Si la salida != -1:
imprimir ("El elemento está en el índice", str (salida))
demás:
imprimir ("El elemento no está disponible en la lista")
Aquí puede ver que el número requerido se encuentra en la posición del índice 2.
Ejemplo 2:
Veamos el enfoque de búsqueda binaria recursiva. El enfoque de recursión se puede utilizar en la búsqueda binaria. Haremos una función recursiva que se llame a sí misma hasta que la condición esté satisfecha. El programa anterior es similar al anterior. Se declaró una función recursiva, así como su condición base,. Calculamos el número medio como lo hicimos en el programa anterior. Para continuar con la búsqueda binaria, utilizamos la declaración if. Se devolverá si el valor medio es equivalente al número que estamos buscando. Si el valor medio está por debajo del valor, lo aumentamos con uno y lo asignamos a bajo usando nuestra función de búsqueda binaria recursiva (). Escribimos nuestro programa principal en la última sección. El procedimiento de búsqueda binaria () ahora requiere 2 parámetros, que es la única modificación del programa anterior. La incapacidad de la función recursiva para asignar valores iniciales a lo bajo, alto y medio es la razón detrás de esto. El valor para esas variables se restablecerá cada vez que se llame a la recursión.
def binary_search (uno, bajo, alto, search_num):Si Bajo Search_num:
return binary_search (uno, bajo, mediano - 1, search_num)
demás:
return binary_search (uno, mid + 1, high, search_num)
demás:
retorno -1
uno = [19, 23, 43, 56, 65, 71, 80]
Search_num = 65
output = binary_search (uno, 0, len (uno) -1, search_num)
Si Search_num != -1:
imprimir ("El elemento está en el índice", str (salida))
demás:
imprimir ("El elemento no está disponible en la lista")
El valor requerido está en el índice 4, como puede ver en la siguiente imagen.
Ejemplo 3:
Otro ejemplo de una técnica de búsqueda binaria, comúnmente conocida como algoritmo de búsqueda de media intervalo, se utiliza para ubicar un valor objetivo dentro de una matriz ordenada. Este programa devuelve verdadero si el número se encuentra en la lista.
def binary_search (my_list, search_num):uno = 0
final = len (my_list) -1
encontrado = falso
mientras (uno<=final and not found):
Mid = (One + Final) // 2
Si my_list [mid] == search_num:
encontrado = verdadero
demás:
Si Search_num
demás:
uno = Mid + 1
regreso encontrado
Impresión (binary_search ([1,2,3,4,5], 3))
Print (binary_search ([11,22,33,44,55], 5))
A continuación se muestra la salida.
Conclusión:
El enfoque más efectivo y rápido para buscar una entrada en una lista es utilizar un algoritmo de búsqueda binario. Se salta sobre la analogía sin sentido. Como dice el nombre, la búsqueda se divide en dos piezas. Se concentra en el lado de la lista más cercano al número que estamos buscando. En la mejor situación, la complejidad del algoritmo de búsqueda binaria es O (1). Esto ocurre cuando el elemento que buscamos aparece en la primera comparación. La peor y promedio de la complejidad del caso de la búsqueda binaria es O (logn). El número total de búsquedas necesarias para localizar el elemento determina esto. Se han discutido diferentes enfoques para determinar la posición del índice de un número dado.