Búsqueda binaria: cómo encontrar un número entre 1 y 1 millón en 20 intentos

Qué es la búsqueda binaria en informática: un ejemplo que le permite encontrar un número de manera eficiente dentro de un conjunto de valores muy grande.

La creación y optimización de algoritmos de búsqueda Es uno de los problemas con los que los desarrolladores siempre se han medido en el campo de las tecnologías de la información: el ordenamiento de los elementos que componen un determinado conjunto es de hecho una de las actividades más caras desde el punto de vista del compromiso de tiempo y máquina. recursos.

Se llama búsqueda binaria (búsqueda binaria en inglés) ese algoritmo que te permite identificar lo que estás buscando en una lista ordenada de elementos.

La búsqueda binaria intenta resolver el problema que ha surgido dividiendo el conjunto de elementos sujetos a verificación varias veces por la mitad hasta que las posibilidades de elección no se reduzcan a una sola.

Para dar un ejemplo concreto que sea fácil de entender, suponga que desea adivinar en qué número entre 1 y 15 está pensando otra persona. Hay como máximo 5 intentos para ganar el desafío.

Imposible utilizar un enfoque randomicoSin embargo, las posibilidades de perder serían demasiado altas. ¿Cómo, entonces, salir siempre ganadores?

Mediante la búsqueda binaria es posible dividir el conjunto de números del 1 al 15 en dos obteniendo el conjunto entre 1 y 7 y entre 8 y 15. Como único elemento debemos saber si la respuesta correcta está en el primero o en el segunda mitad del 'juntos bajo consideración.

Suponiendo que ha elegido 10 como número para adivinar, puede dividir el conjunto 8 ... 15 en dos (8 ... 11 y 12 ... 15). Luego, dividiendo 8 ... 11 en dos (8 ... 9 y 10 ... 11) podrás adivinar el número correcto en solo 4 intentos.

El mismo esquema puede usarse para superar de manera brillante desafíos que solo aparentemente parecen mucho más complejos. Para calcular el número máximo de intentos que se requieren para encontrar el resultado correcto con una búsqueda binaria, simplemente aplique la siguiente fórmula:
n ° máx. intentos = registro2(n + 1)

Una "n" debe reemplazarse por la longitud de la lista o el número de elementos ordenados que contiene. Por lo tanto, con un máximo de solo 20 intentos, es posible adivinar un número elegido del total entre 1 y 1 millón.

Lo simple secuencia de comandos de Python que se puede encontrar en esta página (renombrada a bin_search.py) no hace más que automatizar la operación de búsqueda binaria utilizando un enfoque recursivo.

Primero se genera una matriz que contiene un millón de elementos (generados pseudoaleatoriamente entre 1 y 1,000,000 con la función muestra aleatoria) que se ordena mediante el método clasificar().

Con la linea número = a[5000] hemos optado por adivinar el número en la posición 5000: obviamente, el número de la posición dentro de la matriz se puede modificar y elegir libremente.

El conjunto se divide repetidamente por la mitad utilizando la función bin_search y un enfoque recursivo hasta que encuentre lo que busca.

Búsqueda binaria: cómo encontrar un número entre 1 y 1 millón en 20 intentos

Ejecutando la secuencia de comandos de Python (solo escriba python3 bin_search.py obtendrás una respuesta como "Número N encontrado después de T intentos": como puede ver, para una matriz formada por un millón de elementos, el número máximo de intentos necesarios es solo 20.

La "debilidad" del enfoque presentado consiste precisamente en la necesidad, como se ha destacado varias veces, de ordenar los datos creando así una lista ordenada. Este es uno de los problemas más relevantes en el mundo de la informática, pero la búsqueda binaria sigue siendo un algoritmo eficiente que vale la pena estudiar.

Rate this post
Subir