Algoritmos de búsqueda
Supón que delante de ti hay una fila de tarjetas con números y quieres la tarjeta que lleva un 11. Buscar significa decidir si existe una tarjeta que coincida y, si existe, encontrar una posición donde aparece. Revisar cada tarjeta es una forma de responder. Pero si la fila ya está en orden, ¿podría ese orden decirnos qué posiciones no pueden contener el 11?
01Búsqueda lineal: saber exactamente qué se ha descartado
El valor objetivo es el número que buscamos. Una posición indica dónde está una tarjeta; es distinta de su valor. En la pantalla numeramos las posiciones desde 1. Muchos lenguajes de programación las numeran desde 0, pero eso cambia las etiquetas, no el razonamiento de la búsqueda. Revisa la primera tarjeta. Si su valor coincide con el objetivo, detente; si no, descarta esa posición y pasa a la siguiente.
Antes de cada paso, todas las tarjetas anteriores ya se revisaron y ninguna coincidió. Cada tarjeta sin revisar sigue siendo posible. Esta afirmación se mantiene tras cada comparación fallida, así que si llegamos al final, de verdad no hay coincidencia. Es la razón por la que podemos fiarnos de «no encontrado»; no nos detuvimos solo porque sintiéramos que habíamos buscado bastante.
Todavía no se ha inspeccionado ninguna tarjeta. El rango con borde incluye todos los lugares donde aún podría estar el objetivo.
Cambia la disposición a «Mezclada» y repite. El método sigue funcionando porque nunca supone un orden. Pon el objetivo en 10 para observar un valor ausente. Luego elige de nuevo «De menor a mayor» y pon el objetivo en 2. Ahora está en la primera tarjeta, así que una coincidencia necesita solo una comparación. Si varias tarjetas coinciden, este método de izquierda a derecha devuelve la primera.
02Búsqueda binaria: explicar primero por qué se puede descartar la mitad
Ahora mantén las tarjetas ordenadas de menor a mayor: cada una es igual o menor que la siguiente. Supón que la tarjeta central es 9 y el objetivo es 11. Todo lo que queda a la izquierda de ese 9 es como mucho 9, así que nada puede ser 11. Podemos descartar juntos el centro y todo lo que queda a su izquierda. Si el centro es mayor que el objetivo, el mismo razonamiento descarta el centro y todo lo que queda a su derecha.
Conservamos solo el rango donde aún podría haber una coincidencia. A continuación revisamos su centro, aunque esa posición no tenga por qué ser el centro de la fila original. Si hay dos centros posibles, esta demostración toma el izquierdo. Tras una comparación fallida, el centro revisado también se excluye, así que el rango debe hacerse más pequeño. Cuando el rango queda vacío, el objetivo no existe. Al coincidir se detiene de inmediato; con valores repetidos, puede que no sea la primera posición coincidente.
Todavía no se ha inspeccionado ninguna tarjeta. El rango con borde incluye todos los lugares donde aún podría estar el objetivo.
Prueba con «Mezclada». El experimento deja de aplicar la regla de descarte porque ya no sabemos que todo lo de la izquierda sea menor. Por ejemplo, en la fila mezclada un valor central de 7 no nos dice en qué lado está el 2. El orden es la evidencia que justifica descartar una mitad; elegir un centro por sí solo no basta.
03¿Por qué crece de forma distinta la cantidad de trabajo?
En la búsqueda lineal con tarjetas, tanto una coincidencia en la última posición como un valor ausente necesitan comparaciones. Si se duplica el número de tarjetas, también se duplica ese trabajo en el peor caso. El mejor caso sigue siendo una sola comparación cuando la primera tarjeta coincide. Describen entradas distintas, así que no se contradicen.
En la búsqueda binaria, contemos al revés: con un número limitado de comparaciones, ¿cuántas posiciones como máximo se pueden distinguir? Con cero comparaciones solo se puede tratar una lista vacía. Con una, se puede comprobar una posición central. Con dos, el primer centro ocupa una posición y cada lado puede tener una más, lo que da . Con tres, cada lado puede tener tres, lo que da .
Si es la capacidad para comparaciones, tenemos y . La regla es : se cumple con cero, y al sustituir el valor anterior se obtiene , así que cada caso siguiente también se cumple. Para cubrir posiciones, elige el menor número entero que cumpla . Esta capacidad indica que con menos comparaciones no siempre basta. Todavía falta comprobar que elegir el centro permite alcanzar la cota.
Supón que y . Quitamos la tarjeta central que revisamos. Si es impar, cada lado tiene tarjetas. Si es par, el lado mayor tiene tarjetas; como es impar, un par dentro de la cota es como mucho . En cualquier caso, cada lado tiene como máximo tarjetas. Por tanto, tras una comparación fallida, el lado que queda cabe en la capacidad de comparaciones más. Repite este razonamiento hasta que no queden comparaciones, momento en el que el rango debe estar vacío. Una coincidencia puede detenerse antes. Esto demuestra que la cota también es suficiente. Con ocho tarjetas, tres comparaciones no siempre bastan, pero cuatro siempre alcanzan.
La búsqueda binaria también supone que podemos llegar directamente a una posición central, como en un arreglo: una fila de posiciones de almacenamiento indexadas. Si para llegar al centro hay que recorrer muchos enlaces, un número reducido de comparaciones de valores no garantiza poco trabajo total. Y si los datos no están ordenados, ordenarlos primero cuesta trabajo. Para una sola búsqueda, revisar cada elemento puede ser la tarea más sensata; para búsquedas repetidas sobre datos que no cambian, pagar una vez por ordenar puede resultar útil.
Ver cómo la ordenación crea el orden necesario04Usar la regla y explicar qué permite
Leer el razonamiento
El primer centro es la posición 4, con un 9. Descartamos las posiciones 1–4 porque todas son menores que 14. Quedan las posiciones 5–8; su centro izquierdo es la posición 6, con un 14. Lo encontramos tras dos comparaciones.
Leer el razonamiento
Acabamos de comprobar que su valor no es el objetivo. Conservarlo no añade ninguna posibilidad real y puede impedir que el intervalo se reduzca cuando solo queda una posición. Eliminarlo conserva todas las posibilidades reales y garantiza el avance.
Leer el razonamiento
Cinco comparaciones tienen capacidad , así que caben 31 tarjetas. Con 32, algún objetivo o alguna búsqueda sin éxito necesita una sexta comparación, porque cinco niveles solo ofrecen 31 posiciones centrales que revisar.
