Comparación de búsqueda Binaria, Ternaria, N-aria
BUSQUEDA BINARIA
Este método de búsqueda requiere que los elementos se
encuentren almacenados en una estructura (arreglo, archivo, etc.) de forma ordenada,
es decir clasificados de una determinada manera. En general, si la lista esta
ordenada se puede acortar el tiempo de búsqueda, realizando cuanto mucho log n /
log 2 comparaciones de registros. En
cada ciclo de comparaciones el número de elementos se reduce a la mitad, factor
de 2. Por lo tanto, el número medio
de comparaciones que se realizarán con este método es: (1+(log n/log 2))/2
La búsqueda binaria consiste en comparar el elemento buscado
con el que ocupa en la lista la posición central y, según sea igual, mayor o
menor que el central, para la búsqueda con éxito, o bien, repetir la operación
considerando una sub-lista formada por los elementos situados entre el que
ocupa la posición "central +1" y el ultimo, ambos inclusive, o por lo
que se encuentran entre el primero y el colocado en "central -1", también
ambos inclusive. El proceso termina con búsqueda en fracaso cuando la sub-lista
de búsqueda se quede sin elementos
BUSQUEDA TERNARIA
Análogamente a la búsqueda binaria consiste en comparar
elementos, ahora con dos centros, uno izquierdo y uno derecho. Luego se debe
analizar en qué sub-lista se encuentra el dato buscado, si en la derecha
(centro derecho, final), izquierda (principio, centro izquierdo), o central (centro
izquierdo, centro derecho), y se repetirá hasta encontrar el dato o acabar las
posibilidades, demostrando que el dato no se encuentra en la estructura
analizada.
Codigo en C (Busqueda Ternaria)
BUSQUEDA N-ARIA
Al igual que en la búsqueda binaria y
ternaria este método de búsqueda se diferencia de las ya mencionadas únicamente
en, tomar un número “n” para sub-dividir la lista en “n” partes, a fin de
buscar el valor deseado en una lista de “m” elementos.
Siempre basándose en la formula (log m / log n) para obtener la cantidad máxima de particiones/iteraciones
hechas a las sub-lista, por el programa para encontrar el valor indicado. Dando
por hecho, que el elemento buscado existe dentro de la lista.
Codigo en C (Busqueda N-aria)
Comparación entre
métodos:
Considerando una
cantidad de 1.000.000 de elementos dentro de una lista, se realizó un cuadro
entre el número de particiones a realizar y su cantidad máxima de iteraciones
del método.
Bibliografía:
Joyanes Aguilar, L. and Sánchez García, L. (2006). Programación en C++. Madrid: McGraw-Hill Interamericana de España.
