Python de búsqueda binaria

Funciones y métodos de Python

Una búsqueda binaria de Python encuentra la posición de un elemento en una matriz ordenada. Divide una lista por la mitad. Si un valor especificado es más alto que el número del medio, la búsqueda se enfoca a la derecha de la lista. De lo contrario, la búsqueda busca el número a la izquierda de la lista.

¿Cómo encuentra la posición de un elemento en una lista? Las búsquedas binarias le dan la espalda a eso. Al usar búsquedas binarias, puede encontrar fácilmente la posición de un elemento dentro de una matriz ordenada.

Las computadoras son buenas para buscar en listas para encontrar un elemento específico. Las reglas que utilizan las computadoras para encontrar elementos en una lista se denominan algoritmos de búsqueda. Uno de los algoritmos de Python más populares es la búsqueda binaria.

En esta guía, vamos a discutir qué son las búsquedas binarias y cómo trabajan ellos. Veremos un ejemplo de una búsqueda binaria en Python para que pueda aprender a escribir una en sus programas. ¡Empecemos!




¿Qué es una búsqueda binaria de Python?

Una búsqueda binaria de Python es un algoritmo que encuentra la posición de un elemento en una matriz ordenada. Las búsquedas binarias dividen repetidamente una lista en dos mitades. Luego, una búsqueda compara si un valor es mayor o menor que el valor medio en la lista.

Hay dos formas de realizar una búsqueda binaria. Ambos enfoques establecen punteros que se utilizan para rastrear las posiciones más alta y más baja en un punto particular de una matriz.

El primer enfoque que puede usar es el método iterativo. En este enfoque, se repite un conjunto de declaraciones para determinar la posición de un elemento en una matriz. En Python, usamos un ciclo while para este propósito.

El otro enfoque es el método recursivo. Aquí es donde escribe una función que se llama a sí misma una y otra vez hasta que se encuentra un elemento en una lista. El método recursivo utiliza el enfoque de dividir y conquistar que discutimos anteriormente y repite el proceso de búsqueda hasta que se encuentra un elemento.

El 81% de los participantes dijeron que se sentían más seguros sobre sus perspectivas laborales después de asistir a un campamento de entrenamiento. . Asóciese a un bootcamp hoy mismo.

El graduado promedio de bootcamp pasó menos de seis meses en la transición profesional, desde comenzar un bootcamp hasta encontrar su primer trabajo.

Con todo lo que se habla de dividir y la conquista y la recursividad, puede ser fácil perder de vista cómo funciona exactamente una búsqueda binaria. Por esa razón, vamos a saltar directamente a un ejemplo de cómo funciona la búsqueda binaria. Considere la siguiente lista:

7 9 14 22 34

Vamos a buscar el número & ldquo; 22 & rdquo; en nuestra lista.

Para empezar, vamos a establecer dos punteros en nuestras listas. Un puntero reflejará el valor más alto de la lista y el otro punto reflejará el valor más bajo:

< / table>

Nuestro siguiente paso es encontrar el elemento del medio en la matriz, que es 14. Si este valor es igual al valor que estamos buscando, entonces este valor debería devolverse.

En este caso, 14 no es lo mismo que 22. Por lo tanto, nuestro programa necesita realizar una comparación.


Vamos a comparar el número que estamos buscando con el elemento medio de los elementos en el lado derecho del elemento central actual. Solo haremos esto si el número que estamos buscando es mayor que el número del medio. De lo contrario, compararemos el elemento con el elemento del medio en el lado izquierdo del elemento del medio actual.

El número 22 es mayor que 14. Nuestro programa comienza a comparar 22 al elemento del medio en el lado derecho de nuestro elemento del medio actual (14). En este caso, ese número es 22. Esto es igual al número que estamos buscando.

Hemos encontrado nuestro valor medio. Nuestro programa ahora devolverá la posición de índice de ese número. En este caso, la posición de índice de 22 es 3 (¡recuerde, las listas se indexan comenzando en 0!).




Cómo implementar un binario Buscar en Python

Let & rsq uo; s ensuciarnos las manos con algo de código Python. Vamos a explorar una implementación de Python de una búsqueda binaria utilizando los dos enfoques que discutimos anteriormente: los métodos iterativo y recursivo.

Búsqueda binaria iterativa & nbsp; en Python

Nosotros & rsquo; Comenzaremos con el método iterativo. Aquí es donde recorreremos cada elemento de nuestra lista. Luego, encontraremos el valor medio en la lista. Continuaremos haciéndolo hasta que encontremos el valor que estamos buscando.

Función de búsqueda binaria

Comencemos por definir un función Python para nuestra búsqueda binaria:

 def findValue (números, número_para_encontrar) : low = 0 high = len (listnumbers - 1 while low & lt; = high: middle = low + (high - low) // 2 if numbers [middle] == number_to_find: return middle elif numbers [middle] & lt; number_to_find: low = middle + 1 else: high = middle - 1 return -1 

Nuestra función acepta dos parámetros: la lista a través de la cual queremos buscar y el número que queremos encontrar en nuestra lista.

A continuación, declaramos dos variables de Python que almacenan los valores predeterminados para los valores más bajos y más altos de la lista. < em> low se establece en 0, que es el valor del índice inicial en la lista. high se establece en la longitud de la lista m inus one (porque las listas están indexadas desde cero).

Nuestro siguiente paso fue declarar un bucle while de Python . Este bucle se ejecuta mientras el elemento más bajo es menor o igual que el número más alto. Esto significa que nuestro ciclo solo se ejecutará si nuestro número aún no se ha encontrado.

Luego, calculamos el número del medio. Hacemos esto restando el valor más bajo del valor más alto. Luego calculamos el módulo (resto) de ese número cuando lo dividimos por 2. Luego, agregamos el módulo al valor del número más bajo.

Si el número del medio en nuestra lista es el mismo que el número que queremos encontrar, devolvemos la posición de ese número.

Establecemos nuestro nuevo & ldquo; bajo & rdquo; número para ser igual a uno mayor que la posición media. Esto sucede si el número del medio es menor que el número que queremos encontrar. Esto mueve nuestra búsqueda hacia el lado izquierdo de nuestra lista, como hicimos en nuestro ejemplo visual anterior.


De lo contrario, establecemos nuestro número & ldquo; alto & rdquo; para que sea igual a uno menos que la posición media. Esto mueve nuestra búsqueda al lado derecho de nuestra lista.

" Career Karma entró en mi vida cuando más lo necesitaba y rápidamente me ayudó a combinar con un bootcamp. ¡Dos meses después de graduarme, encontré el trabajo de mis sueños que se alineaba con mis valores y metas en la vida! "

Venus, ingeniero de software en Rockbot

Esto se repite hasta que low es igual o menor que high. Si no se encuentra nuestro valor, devolvemos -1. Hablaremos sobre por qué en un minuto.

Ejecutar la búsqueda

Agregue el siguiente código al final de su programa, fuera de la función findValue :

 numbers = [7, 9, 14, 22, 34] number_to_find = 22 final = findValue (numbers, number_to_find) if final == -1: print (" Este elemento no se encontró en la lista. ") else: print ("El número" + str (number_to_find) + "se encontró en la posición del índice" + str (final) + ".") 

Hemos comenzado declarando la lista de elementos a través de los cuales queremos buscar. Luego, hemos especificado el número que queremos encontrar, que es 22.

A continuación, llamamos a nuestra función findValue () a y pasar a través de él la lista.

Aquí es donde viene el -1 de antes. Si el número devuelto por nuestra función es -1, eso significa que nuestro elemento no se encontró en la lista. Los programadores a menudo usan -1 en situaciones como esta porque nuestra función de búsqueda no puede devolver un número negativo.

De lo contrario, nuestro programa imprime un mensaje que nos indica la posición de índice de ese valor.

Nuestro código devuelve:

 El número 22 se encontró en la posición del índice 3. 

Ahora sabemos que el número 22 aparece en la posición del índice 3.

Búsqueda binaria recursiva en Python

También podemos usar la recursividad para realizar una búsqueda binaria. Aquí es donde definiremos una función que se sigue llamando a sí misma hasta que una condición & ndash; nuestro número encontrado & ndash; 

Definir una función recursiva

Como en nuestro último ejemplo, comenzaremos escribiendo una función que realiza nuestra búsqueda binaria:

 def findValue (numbers, number_to_find, low, high): if high & gt; = low: middle = low + (high - low) // 2 si los números [en el medio] == número_para_encontrar: devuelve los números elif del medio [en el medio] & lt; number_to_find: return findValue (números, number_to_find, medio + 1, alto) else: return findValue (números, número_to_find, bajo, medio - 1) else: return -1 

Nuestro código es algo similar a nuestro último ejemplo.

Comenzamos verificando si el valor más alto es mayor o igual a bajo. Si es así, nuestro programa devolverá -1. De lo contrario, comenzará a realizar una búsqueda binaria.

Calculamos el número del medio usando el mismo enfoque que en el último ejemplo. Primero, restamos el valor más bajo del más alto. Luego, calculamos el módulo (resto) de ese valor cuando se divide por 2. Finalmente, agregamos el número más bajo.

Luego escribimos una declaración if que decide cómo nuestra búsqueda binaria debe continuar:

  • Si el número del medio es igual al que estamos buscando, se devuelve la posición de ese número.
  • Si el número del medio es menos que el que estamos buscando, se llama de nuevo a nuestra función findValue () . Esta vez, el valor de bajo se establece para ser igual a uno mayor que nuestro valor medio.
  • Si el número del medio es mayor que el que estamos buscando, el < Se llama a la función em> findValue () . El valor de & ldquo; alto & rdquo; será igual a uno menos que el valor medio.

Escribir el programa principal

Todo lo que nos queda por hacer es escribir nuestro programa principal:

 números = [7, 9, 14, 22, 34] número_a_encontrar = 22 final = findValue (números, número_a_encontrar, 0, len (números) - 1) si final == - 1: print ("Este elemento no se encontró en la lista.") Else: print ("El número" + str (number_to_find) + "se encontró en la posición de índice" + str (final) + ".")   

Nuestro programa principal es el mismo que nuestro ejemplo anterior, salvo una diferencia. Estamos pasando dos nuevos parámetros a nuestra función findValue () : bajo y alto.

Necesitamos hacer esto porque nuestro algoritmo es recursivo y no podemos asignar esos valores en nuestra función. Si asignáramos los valores en nuestra función, esos valores se restablecerían cada vez que nuestra función se ejecutara, lo que romper nuestro algoritmo de búsqueda.

Nuestro código devuelve:

 El número 22 se encontró en posición del índice 3. 

Hemos recibido el mismo resultado de antes. En este ejemplo, hemos utilizado un programa recursivo en lugar de un programa iterativo para realizar nuestra búsqueda binaria.




¿Cuándo debería utilizar una búsqueda binaria de Python?

Una búsqueda binaria es una forma eficiente de buscar a través de una lista de números. Esta búsqueda es más eficiente que una búsqueda lineal. Esto se debe a que el método binario reduce su búsqueda a la mitad tan pronto como encuentra la mitad de una lista ordenada.

Es importante tener en cuenta que una lista debe ordenarse numéricamente antes de que se pueda buscar usando una búsqueda binaria. Antes de realizar una búsqueda binaria, asegúrese de que sus números estén ordenados en orden ascendente.




Búsqueda binaria en Python Complexity Breakdown

¿Cuál es la complejidad de una búsqueda binaria? Esa es una buena pregunta.

El algoritmo de búsqueda binaria tiene una complejidad de O (1) en el mejor de los casos. Esto ocurre cuando la primera comparación es igual al elemento que está buscando.

La complejidad promedio y en el peor de los casos para una búsqueda binaria es O (log n). Esto significa que el tiempo que lleva realizar una búsqueda aumenta logarítmicamente dependiendo de cuántos elementos hay para buscar en una lista.




Conclusión

Las búsquedas binarias son una forma eficiente para encontrar la posición de índice de un valor en una lista.

Cada vez que se ejecuta una búsqueda binaria, la búsqueda dividirá la lista en dos partes. La búsqueda se centra en el lado de la lista más cercano al número que está buscando.

Cada vez que se ejecuta la búsqueda, la cantidad de números a través de los cuales el programa necesita buscar se reduce a la mitad.

Para obtener más información sobre Python, lea nuestra guía de Cómo aprender Python .





Python de búsqueda binaria: StackOverflow Questions

Bajo


Alto
7 9 14 22 34