Búsqueda binaria multiplicativa - Multiplicative binary search
 Visualización del algoritmo de búsqueda binaria multiplicativa donde 7 es el valor objetivo.
| |
| Clase | Algoritmo de búsqueda |
|---|---|
| Estructura de datos | Formación |
| Rendimiento en el peor de los casos | O (log n ) |
| Rendimiento en el mejor de los casos | O (1) |
| Rendimiento medio | O (log n ) |
| Complejidad espacial en el peor de los casos | O (1) |
En informática , la búsqueda binaria multiplicativa es una variación de la búsqueda binaria que utiliza una permutación específica de claves en una matriz en lugar del orden de clasificación utilizado por la búsqueda binaria normal. La búsqueda binaria multiplicativa fue descrita por primera vez por Thomas Standish en 1980. Este algoritmo se propuso originalmente para simplificar el cálculo del índice de punto medio en computadoras pequeñas sin operaciones eficientes de división o desplazamiento. En el hardware moderno, la naturaleza compatible con la caché de la búsqueda binaria multiplicativa la hace adecuada para la búsqueda fuera del núcleo en el almacenamiento orientado a bloques como alternativa a los árboles B y B + . Para un rendimiento óptimo, el factor de ramificación de un árbol B o árbol B + debe coincidir con el tamaño de bloque del sistema de archivos en el que está almacenado. La permutación utilizada por la búsqueda binaria multiplicativa coloca el número óptimo de claves en el primer bloque ( raíz ), independientemente del tamaño del bloque.
Algunos compiladores de optimización utilizan la búsqueda binaria multiplicativa para implementar instrucciones de cambio .
Algoritmo
La búsqueda binaria multiplicativa opera en una matriz ordenada permutada. Las claves se almacenan en la matriz en la secuencia de orden de nivel del árbol de búsqueda binaria balanceada correspondiente . Esto coloca el primer pivote de una búsqueda binaria como el primer elemento de la matriz. Los segundos pivotes se colocan en las siguientes dos posiciones.
Dada una matriz A de n elementos con valores A 0 ... A n -1 , y el valor objetivo T , la siguiente subrutina utiliza multiplicativo búsqueda binaria para encontrar el índice de T en A .
- Establecer i en 0
- si i ≥ n , la búsqueda termina sin éxito.
- si A i = T , se realiza la búsqueda; volver i .
- si A i < T , establezca i en 2 × i + 1 y vaya al paso 2.
- si A i > T , establezca i en 2 × i + 2 y vaya al paso 2.
Ver también
- Árbol de búsqueda binaria : estructura de datos en forma de árbol ordenada para una búsqueda rápida
- Métodos para almacenar árboles binarios
- Ahnentafel : sistema de numeración genealógica para enumerar los antepasados directos de una persona