Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 2: Búsqueda binariaBúsqueda binaria
La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada de elementos. Funciona al dividir repetidamente a la mitad la porción de la lista que podría contener al elemento, hasta reducir las ubicaciones posibles a solo una. Usamos la búsqueda binaria en el juego de adivinar en la lección introductoria.
Una de las maneras más comunes de usar la búsqueda binaria es para encontrar un elemento en un arreglo. Por ejemplo, el catálogo estelar Tycho-2 contiene información acerca de las 2,539,913 estrellas más brillantes en nuestra galaxia. Supón que quieres buscar en el catálogo una estrella en particular, con base en el nombre de la estrella. Si el programa examinara cada estrella en el catálogo estelar en orden empezando con la primera, un algoritmo llamado búsqueda lineal, la computadora podría, en el peor de los casos, tener que examinar todas las 2,539,913 de estrellas para encontrar la estrella que estás buscando. Si el catálogo estuviera ordenado alfabéticamente por nombres de estrellas, la búsqueda binaria no tendría que examinar más de 22 estrellas, incluso en el peor de los casos.
Los siguientes artículos discuten cómo describir cuidadosamente el algoritmo, cómo implementar el algoritmo en JavaScript y cómo analizar su eficiencia.
Describir la búsqueda binaria
Al describir un algoritmo para un ser humano, a menudo es suficiente una descripción incompleta. Algunos detalles pueden quedar fuera de una receta de un pastel; la receta supone que sabes cómo abrir el refrigerador para sacar los huevos y que sabes cómo romper los huevos. La gente puede saber intuitivamente cómo completar los detalles faltantes, pero los programas de computadora no. Es por eso que necesitamos describir completamente los algoritmos computacionales.
Para poder implementar un algoritmo en un lenguaje de programación, necesitarás entender un algoritmo hasta sus últimos detalles. ¿Cuáles son las entradas del problema? ¿Las salidas? ¿Qué variables deben crearse, y qué valores iniciales deben tener? ¿Qué pasos intermedios deben tomarse para calcular otros valores y calcular en última instancia la salida? ¿Estos pasos repiten instrucciones que se pueden escribir en forma simplificada al usar un bucle?
Veamos cómo describir cuidadosamente la búsqueda binaria. La idea principal de la búsqueda binaria es llevar un registro del rango actual de intentos razonables. Digamos que estoy pensando en un número entre uno y 100, justo como en el juego de adivinar. Si ya intentaste decir 25 y te dije que mi número es más grande, y ya intentaste decir 81 y te dije que mi número es más chico, entonces los números en el rango de 26 a 80 son los únicos intentos razonables. Aquí, la sección roja de la recta numérica contiene los intentos razonables, y la sección negra muestra los intentos que hemos descartado:
En cada turno, haces un intento que divide el conjunto de intentos razonables en dos rangos de aproximadamente el mismo tamaño. Si tu intento no es correcto, entonces te digo si es muy alto o muy bajo, y puedes eliminar aproximadamente la mitad de los intentos razonables. Por ejemplo, si el rango actual de los intentos razonables es de 26 a 80, intentarías adivinar a la mitad del camino, left parenthesis, 26, plus, 80, right parenthesis, slash, 2, o 53. Si después te digo que 53 es demasiado alto, puedes eliminar todos los números de 53 a 80, dejando 26 a 52 como el nuevo rango de intentos razonables, reduciendo a la mitad el tamaño del rango.
Para el juego de adivinar, podemos llevar un registro del conjunto de intentos razonables al usar unas cuantas variables. Sea la variable m, i, n el intento razonable mínimo actual para esta ronda, y sea la variable m, a, x el intento razonable máximo actual. La entrada (o input en inglés) al problema es el número n, el mayor número posible que tu oponente está pensando. Suponemos que el menor número posible es uno, pero sería fácil modificar el algoritmo para tener el menor número posible como una segunda entrada.
Aquí está una descripción paso a paso de cómo usar la búsqueda binaria para jugar el juego de adivinar:
- Sea m, i, n, equals, 1 y m, a, x, equals, n.
- Adivina el promedio de m, a, x y m, i, n, redondeado hacia abajo de modo que sea un entero.
- Si adivinaste el número, detente. ¡Lo encontraste!
- Si el intento fue demasiado bajo, haz que m, i, n sea uno más grande que el intento.
- Si el intento fue demasiado alto, haz que m, a, x sea uno menos que el intento.
- Regresa al paso dos.
Podríamos hacer que la descripción fuera todavía más precisa al describir claramente las entradas y las salidas del algoritmo y al clarificar qué queremos decir con instrucciones como "adivina un número" y "detente". Pero esto es suficiente detalle por ahora.
A continuación, vamos a ver cómo podemos utilizar la búsqueda binaria en un arreglo, y discutir discutir cómo convertir las descripciones de los algoritmos a código real que funcione.
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom junto con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
- como se encuentran los binarios(2 votos)
- son las respuestas a las preguntas. Por ejemplo si se quiere adivinar un numero del 1 al 10. Se preguntaria X<5? . Si la respuesta es si se considera como 1 y si la respuesta es no se considera como 0. Asi se va formado un binario que representaria cada uno de los posibles numeros. Puedes investigar más sobre esto buscando arboles lógicos o árboles de decisión.(17 votos)
- Interesante el articulo de entradas y salidas y ver cual es la mas importante. Perfecto.(4 votos)
- lo que explica es que a parte de la búsqueda lineal existe la binaria. lo que hace es }por medio de formulas de división mas que todo. ubicar el numero adivinar por medio de rangos y no de uno en uno. espero le sirva la respuesta.(3 votos)
- hay ejemplos de codigo fuente?(3 votos)
- 78864<asiertos cuantos crees que arias 9 como algoritmo(0 votos)
- pues me hizo saber que la busqueda binaria es un algoritmo eficiente, y se hace dividiendo, y e igual saber que el pseudocodigo es mas preciso en entrada y salidas este me gusta mas que otros(2 votos)
- explica es que a parte de la búsqueda lineal existe la binaria. lo que hace es por medio de formulas de división mas que todo. ubicar el numero adivinar por medio de rangos y no de uno en uno. espero que ayude a alguien o un grupo de personas :3(2 votos)
- ¿Se puede modificar el algoritmo que ya esta instalado en cualquier programa?(1 voto)
- En algunos casos no se puede cambiar el algoritmo en los programas ya realizados por terceros debido a que ellos tienen los códigos del mismo y son 'secretos', pero si es un programa de código abierto claro que se puede :)(1 voto)
- para que nos sirve la busqueda binaria(1 voto)
- Es sencillo, declara un rango un ejemplo 500 luego dividelo por 2 eso daria 250 entonces pregunta el numero que piensas es mayor que 250 si es asi ya conoces que tu minimo es 250 y tu maximo 500 entonces divide 250 entre 2 eso da 125, en ese caso sumaselo a tu variable minimo y nos daria 375 esto lo hago para que el numero este dentro del rango, ahora pregunta el numero es mayor a 375 en caso de que no sea asi ya sabes que tu minimo es 250 y tu maximo 375 y asi sucesivamente(3 votos)
- que significa los código que aparecen en el texto(1 voto)