¿Hay un nombre para este tipo de búsqueda binaria?

Question

Al escribir un código hoy, me he encontrado con una circunstancia que me ha llevado a escribir una búsqueda binaria de una clase que nunca había visto antes. ¿Esta búsqueda binaria tiene un nombre, y es realmente una búsqueda "binaria"?

motivación

En primer lugar, con el fin de hacer la búsqueda más fácil de entender, voy a explicar el caso de uso que dio lugar a su creación.

Supongamos que tiene una lista de números pedidos. Se le pide que encuentre el índice del número en la lista más cercana a x.

int findIndexClosestTo(int x); 

Las llamadas a findIndexClosestTo()siempre seguir esta regla:

Si el último resultado de findIndexClosestTo() era i, a continuación, los índices más cerca de i tienen mayor probabilidad de ser el resultado de la llamada actual a findIndexClosestTo().

En otras palabras, es más probable que el índice que necesitamos encontrar esta vez sea más cercano al último encontrado que alejado de él.

Por ejemplo, imagine un niño simulado que camina hacia la izquierda y hacia la derecha en la pantalla. Si a menudo estamos consultando el índice de la ubicación del niño, es probable que esté cerca del último lugar donde lo encontramos.

Algoritmo

Dado el caso anterior, sabemos que el último resultado de findIndexClosestTo() era i (si ésta es realmente la primera vez que la función se ha llamado, i por defecto el índice medio de la lista, por simplicidad, aunque una búsqueda binaria separada para encontrar el resultado de la primera llamada en realidad sería más rápida), y la función ha sido llamada nuevamente. Teniendo en cuenta el nuevo número x, seguimos este algoritmo para encontrar su índice:

1. interval = 1;
2. es el número que estamos buscando, x, posicionada en i? Si es así, devuelva i;
3. De lo contrario, determine si x está por encima o por debajo de i. (Recuerde, la lista está ordenada.)
4. Mueva interval índices en la dirección de x.
5. Si hemos encontrado x en nuestra nueva ubicación, devolvemos esa ubicación.
6. Doble interval. (Es decir interval *= 2)
7. Si hemos pasado x, volver interval índices, establezca interval = 1, vaya a 4.

Teniendo en cuenta la regla de probabilidad se ha dicho (bajo el encabezado de motivación), esto parece a mí ser la forma más eficiente de encontrar el índice correcto. ¿Conoces una manera más rápida?

Answer 1

Lo que está haciendo es (en mi humilde opinión) una versión de Interpolation search

En una búsqueda de interpolación se asume números se distribuyen por igual, y que a continuación, trate de adivinar la ubicación de un número desde el primer y último número y la longitud de la matriz.

En su caso, está modificando el interpolation-algo de modo que suponga que la clave está muy cerca del último número que buscó.

También tenga en cuenta que su algo es similar a algo donde TCP trata de encontrar el tamaño de paquete óptimo. (No recuerdo el nombre :()

1. inicio lento
   1. doble del intervalo
   2. si el paquete no reiniciar desde el último tenido éxito packet./ Reinicie a partir del tamaño de paquete predeterminado .. 3.

Answer 2

Esto está hablando de la parte superior de mi cabeza, así que no tengo nada que respalde sino la intuición.

En el paso 7, si hemos pasado x, puede ser más rápido para reducir a la mitad interval, y la cabeza vuelta hacia x - efectivamente, interval = -(interval/2), en lugar de restablecer interval a 1.

Voy a tener que dibujar algunos números en papel, sin embargo ...

Editar: Disculpas - Estoy diciendo tonterías arriba: ¡ignórame! (Y me iré y tendré un apropiado piénselo esta vez ...)

Answer 3

En el peor de los casos, su algoritmo es O ((log n)^2).

Supongamos que se inicia a 0 (con intervalo = 1), y el valor que busca en realidad reside en la posición 2^n - 1.

En primer lugar se echa 1, 2, 4, 8, ... , 2^(n-1), 2^n. Vaya, eso se dispara, así que regrese a 2^(n-1).

A continuación, marque 2^(n-1) +1, 2^(n-1) +2, ..., 2^(n-1) + 2^(n-2), 2^(n-1) + 2^(n-1). Ese último término es 2^n, así que ¡Ups !, eso pasó de nuevo. Regrese a 2^(n-1) + 2^(n-2).

Y así sucesivamente, hasta llegar finalmente a 2^(n-1) + 2^(n-2) + ... + 1 == 2^n - 1.

La primera exceso tomó registro n pasos. El siguiente tomó (log n) -1 pasos. El siguiente tomó (log n) - 2 pasos. Y así.

Entonces, en el peor de los casos, tomó 1 + 2 + 3 + ... + log n == O ((log n)^2) pasos.

Una mejor idea, creo, es cambiar a la búsqueda binaria tradicional una vez que se sobrepase la primera vez. Esto preservará el peor rendimiento del algoritmo de O (log n), mientras tiende a ser un poco más rápido cuando el objetivo está realmente cerca.

No conozco un nombre para este algoritmo, pero me gusta. (Por una extraña coincidencia, podría haber utilizado ayer. Realmente.)

Answer 4

Su rutina es típico de las rutinas de interpolación. No pierde mucho si lo llama con números aleatorios (~ búsqueda binaria estándar), pero si lo llama con números que aumentan lentamente, no le llevará mucho encontrar el índice correcto.

Esto es, por lo tanto, un comportamiento predeterminado razonable para buscar una tabla ordenada con fines de interpolación.

Este método se discute con gran detalle en la tercera edición de las Recetas Numéricas, sección 3.1.