Búsqueda binaria: dividir la búsqueda por la mitad — Informática, 7–10
Cuando una lista ya está ordenada, no necesitas comprobar cada elemento uno por uno. La búsqueda binaria mira el centro, decide en qué mitad puede estar la respuesta y repite el proceso hasta encontrarla o descartar que exista.
Dividir las posibilidades por la mitad
Imagina que un número secreto está escondido en una fila ordenada. En vez de empezar por el primero, pregunta por el que está en el centro. Si tu objetivo es mayor, descarta la mitad inferior; si es menor, la superior. Cada respuesta elimina aproximadamente la mitad de las opciones y la búsqueda se hace pequeña enseguida.
¿Por qué no comprobar cada elemento?
Empezar por el principio funciona en una lista corta, pero se vuelve lento con miles o millones de elementos ordenados. La búsqueda binaria usa el orden como pista en vez de desperdiciarlo. Nace de una pregunta sensata: ¿cómo podemos descartar tantos lugares equivocados como sea posible con una sola comprobación?
Encontrar 73 en una lista
La lista ordenada es 12, 25, 31, 44, 58, 73, 81, 90. Primero, comprueba el centro: 44. Como 73 es mayor, conserva 58, 73, 81, 90. Comprueba el centro de esos números: 73. Encuentras el objetivo tras dos comprobaciones, en vez de revisar los ocho desde el principio.
El orden es imprescindible
Es razonable usar el centro de cualquier lista, porque parece un atajo útil. Pero si la lista es 12, 90, 25, 73, 44, 81, 31, 58, ver 44 no te dice en qué mitad está 73. La búsqueda binaria solo funciona cuando la lista está ordenada según aquello que estás comparando.
Encontrar cosas rápidamente
Un diccionario usa el orden alfabético, así que puedes abrirlo cerca del centro y reducir la búsqueda de una palabra. Los programas usan la misma estrategia con nombres, números y registros ordenados. Es útil cuando la lista es grande y ya está ordenada; ordenarla primero puede costar trabajo extra, así que el atajo no siempre conviene.
Sigue explorando
Otros idiomas
Cargando MyLeoNes™…