Hispanopedia WikiEn ciencias de la computación , la búsqueda binaria multiplicativa es una variación de la búsqueda binaria que utiliza una permutación específica de claves en un arreglo en lugar del orden ordenado utilizado por la búsqueda binaria regular. [ 1 ] La búsqueda binaria multiplicativa fue descrita por primera vez por Thomas Standish en 1980. Este algoritmo fue propuesto originalmente para simplificar el cálculo del índice de punto medio en computadoras pequeñas sin operaciones eficientes de división o desplazamiento. En hardware moderno, la naturaleza amigable con la caché de la búsqueda binaria multiplicativa la hace adecuada para la búsqueda fuera de la memoria principal en almacenamiento orientado a bloques como una alternativa a los árboles B y árboles 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 optimizadores utilizan la búsqueda binaria multiplicativa para implementar sentencias switch . [ 2 ] [ 3 ]
Algoritmo
La búsqueda binaria multiplicativa opera sobre un arreglo ordenado y permutado. Las claves se almacenan en el arreglo siguiendo la secuencia de niveles del árbol de búsqueda binaria balanceado correspondiente . Esto sitúa el primer pivote de la búsqueda binaria como el primer elemento del arreglo. Los segundos pivotes se ubican en las dos posiciones siguientes.
Dado un arreglo A de n elementos con valores A 0 ... A n −1 , y un valor objetivo T , la siguiente subrutina utiliza una búsqueda binaria multiplicativa para encontrar el índice de T en A .
- Establecer i en 0
- Si i ≥ n , la búsqueda finaliza sin éxito.
- Si A i = T , la búsqueda ha terminado; devuelve i .
- Si A i > T , establece i en 2× i + 1 y ve al paso 2.
- Si A i < T , establece i en 2× i + 2 y ve al paso 2.
Véase también
- Árbol de búsqueda binaria : estructura de datos de árbol binario con raíz.
- Métodos para almacenar árboles binarios : forma limitada de estructura de datos de árbol.
- Ahnentafel : sistema de numeración genealógica para enumerar los antepasados directos de una persona.
Citas
- ↑ Standish, Thomas A. (1980). «Capítulo 4.2.2: Búsqueda en tabla ordenada». Técnicas de estructura de datos . Addison-Wesley. págs. 136–141 . ISBN 978-0201072563.
- ↑ Sayle, Roger A. (17 de junio de 2008). "Análisis de superoptimizador de la generación de código de ramificación múltiple" ( PDF) . Actas de la Cumbre de Desarrolladores de GCC : 103–116 . Recuperado el 4 de marzo de 2017 .
- ↑ Spuler, David A. (enero de 1994). Generación de código de compilador para sentencias de bifurcación múltiples como un problema de búsqueda estática (Informe técnico). Departamento de Ciencias de la Computación, Universidad James Cook, Australia. 94/03.
- Algoritmos de búsqueda
