Búsqueda binaria.Código:Int binaria(int A[],int clave, int inf, int sup){         al ser recursivo hemos de actualizar límites. If (inf>sup)Return -1;Medio = (inf+sup)/2;If (claveA[medio])Return binaria(A,clave,medio+1,sup);Return medio;

Ejemplo

:  busca el  y el .El orden de llamada es: Binaria(A,25,0,8), binaria(A,25,5,8). La función devuelve 6.[medio])return>

El orden de llamada es binaria (A,7,0,8), binaria(A,7,0,3), binaria(A,7,2,3), binaria (A,7,3,3), binaria(A,7,3,2). Como inf>sup entramos en el if y la función devuelve -1.

Tablas hash

De cada estructura elijo un campo que identifica de forma unívoca a esa estructura. Una función hash se aplica a la clave y devuelve la posición de la tabla donde está almacenada esa clave. Para dos clavesdistintas la función hash ha de devolver posiciones distintas, es decir, no debe haber colisiones. Esto se llama factor de carga  donde  es el número de elementos almacenados y  es el tamaño de la tabla. Lo recomendable es que , es decir que el  de la tabla esté vacía para poder arreglar las colisiones que surjan.Así:  Donde   es el conjunto de claves y  son las posiciones dentro del vector.

Propiedades

A una función hash se le pedirá que no tenga muchas colisiones y que el tiempo de evaluación sea constante.

Tipos de funciones Hash

Aritmética modular

 donde  es el tamaño de la tabla. Es recomendable que el tamaño no sea un múltiplo de 2 ni un múltiplo de 10. Lo óptimo tendrá que ser el número primo más cercano que cumpla el factor de carga.

Ejemplo

: Considerar una aplicación en la que hay que almacenar 800 registros. El campo clave elegido es el número de identificación. Elegir el tamaño de la tabla de dispersión y utilizar aritmética modular para calcular la posición que ocupan los elementos cuyo número de identificación es el siguiente.245643. Hemos de elegir un número primo cercano. Elegimos el 997.. El resto es y es la posición de la tabla donde se alojará el número.

Método del plegamiento

.Donde  son trozos de la clave.

Ejemplo

: Los registros de pasajeros de un tren de largo recorrido se identifican por un campo de  dígitos que se va a utilizar como clave para crear una tabla hash de 1.000 posiciones. Se utiliza como función hash el método del plegamiento haciendo grupos de  dígitos. Aplicar esta función a los registros y ver en qué posición quedan... Como no cabe en la tabla de  hago módulo .

Método de la mitad del cuadrado

Calculamos el cuadrado de la clave: Elegir dígitos en determinadas posiciones.

Ejemplo

: Aplicar el método de mitad del cuadrado a los mismos registros del ejercicio anterior eligiendo los dígitos que se encuentran en las posiciones  empezando a numerar por la derecha. 

Método de la multiplicación

Se multiplica  donde Coger parte decimal a la que llamamos .Multiplicamos .Coger parte entera.

Ejemplo

: con ...

Resolución de colisiones Encadenamiento

Cuando dos valores distintos van a una misma posición en la tabla hash puedo hacer que en esa posición de la tabla haya una lista enlazada que tenga todos los elementos que ocupen esa posición.

Direccionamiento abierto

Cuando calculamos la función hash nos da una posición y esa está ocupada lo que hacemos es probar con una lista de posiciones que se llama secuencia de sondeo.

Sondeo lineal

Inserción

Clave  y .La primera posición que probamos es  Si  está ocupada probamos con  etc. Puede ocurrir que lleguemos al final de la tabla. Cuando llegamos no paramos, probamos con la , luego con la  hasta llegar a  si hace falta.

Ejemplo

: Existen  elementos cuyas claves son . Para cada una de ellas la función Hash que utilizamos genera los siguientes valores:

Buscar

Empezamos por . Si coincide lo hemos encontrado. Si no seguimos la secuencia de sondeo. Si llegamos de nuevo a la posición  o a una posición vacía podemos decir que no está en la lista.

Definición

Un agrupamiento primario ocurre cuando hay varias posiciones consecutivas ocupadas. Esto implica que para encontrar un sitio libre hay que pasar varias posiciones para llegar a un sitio vacío. Además una vez lo encuentro y añado otro nuevo el problema se complica porque tendré un agrupamiento primario un poco más largo. Lo solucionaremos con el siguiente tipo de sondeo.

Sondeo cuadrático

Inserción

Clave  y .La primera posición que probamos es  Si  está ocupada probamos con   . Puede ocurrir que lleguemos al final de la tabla. Cuando llegamos al final no paramos, cogemos el resto.

Ejemplo

: Tenemos una tabla de tamaño Sondeo.

Inserción

Clave  y  y . Probamos con Ejemplo
: Para resolver colisiones se utiliza el método de doble dispersión, el primero es aritmética modular y el segundo el método de la multiplicación. Encontrar los elementos con las claves  en una tabla de tamaño .