Algoritmos de Búsqueda y Organización de Datos: Binaria, Secuencial y Hashing

Búsqueda Binaria (Binary Search)

La búsqueda binaria se utiliza sobre un array ordenado y reduce significativamente el tiempo de búsqueda, ya que disminuye el número de iteraciones necesarias.

Funcionamiento y RRN

El procedimiento consiste en lo siguiente: se compara el elemento a buscar con un elemento cualquiera en el arreglo (generalmente el punto medio). Si el valor de este es mayor que el del elemento buscado, se repite el procedimiento en la mitad correspondiente. En caso contrario, se toma la parte del array que va desde el elemento tomado hasta el final. Por lo tanto, obtenemos intervalos cada vez más pequeños hasta obtener un tamaño indivisible (punto medio, división entre 2).

Ventajas

• Recomendado para buscar en arreglos muy grandes.
• Reduce el tiempo requerido para buscar en una lista.
• Es rápido debido a su naturaleza recursiva.

Desventajas

• El archivo debe estar obligatoriamente ordenado.
• No revisa todos los elementos del archivo de forma secuencial.

Búsqueda Secuencial

Este método se utiliza cuando el array no está ordenado. Consiste en buscar el elemento comparándolo secuencialmente con cada elemento del arreglo hasta encontrarlo o hasta que se llegue al final del mismo.

Ventajas y Desventajas

• Ventaja: Es el método recomendado para buscar en arreglos en los que los archivos no están ordenados.
• Desventaja: Es un proceso muy lento y requiere mucho tiempo, ya que compara los elementos uno a uno.

KeySorting

El KeySorting se usa para ordenar datos de archivos que no caben completos en la memoria principal. Para ello, se toma una llave de cada dato y se le asigna un RRN (Relative Record Number) que apunta a la dirección en el disco. De esta forma, se ordenan todas las llaves en una estructura tal que, al hacer una búsqueda de una llave, esta te envíe directamente a la dirección correspondiente en el disco.

Indexación (Index)

La indexación es una técnica para recuperar los datos contenidos en un fichero o en una zona de memoria por medio de un índice que guarda la posición exacta de los datos.

Hashing (Método de Búsqueda Hash)

El término Hash se refiere a una función o método para generar claves que representen de manera casi unívoca a un archivo, registro, etc. (su función es resumir o identificar un dato). Este método aumenta la velocidad de búsqueda de un registro en un arreglo, permitiendo la eliminación e inserción de nuevos registros de forma eficiente. No requiere que los elementos estén ordenados, pues consiste en asignar a cada elemento un índice mediante una transformación del elemento (función hash).

Ventajas del Hashing

• Se pueden usar los valores naturales de la llave.
• No se requiere almacenamiento adicional para los índices.

Desventajas del Hashing

• No pueden usarse registros de longitud variable.
• No permite llaves repetidas.
• Solo permite el acceso por una sola llave.

Comparativa: Índice vs. Hashing

Características del Índice

• Impone el orden en un archivo sin tener que reorganizar el archivo físicamente.
• Requiere varios ingresos (accesos) a disco.
• Cuando un archivo se modifica, cada índice en el archivo debe modificarse.
• Presenta ineficiencia al insertar y eliminar registros.

Características del Hashing

• No existe un orden físico en el archivo.
• Requiere un solo ingreso (acceso) a disco.
• Cuando el archivo se modifica, los índices no se modifican.
• Ofrece alta eficiencia al insertar y eliminar registros.