Unidad 7: Métodos de Búsqueda Parte 1

Unidad 7: Métodos de Búsqueda.

Búsqueda Lineal.

Consiste en ir comparando el elemento o criterio de búsqueda con cada uno de los elementos en el arreglo, esto se hace recorriendo el arreglo y deteniéndose en cada elemento y hacer la comparación, en caso de ser verdadera la comparación, guardar la posición el elemento o dato.

Implementación:

public  int busquedaSecuencial(int []arreglo,int dato){

 int posicion = -1;

  for(int i = 0; i < arreglo.length; i++){//recorremos todo el arreglo

      if(arreglo[i] == dato){//comparamos el elemento en el arreglo con el buscado

    posicion = i;//Si es verdadero guardamos la posicion

    break;//Para el ciclo

   }

 }

 return posicion;

}

Este método nos halla la posición del elemento o dato buscado pero en su primero coincidencia, si queremos que nos halle la posición de la última coincidencia, lo único que tenemos que hacer es eliminar la línea donde aparece 'break'.Si el resultado del método anterior es -1, significa que el elemento no se encuentra en el arreglo.

Algoritmo:

R= Inicio.

i=0.

Bandera = 0.

Mientras 1<n

Si n[i]=x

Inicio

Desplegar “búsqueda exitosa y el dato es”, x.

Desplegar “y se encuentra en la posición”, i=n.

Bandera=1.

Else

I=i+1.

Fin

Fin

Si bandera=0

Desplegar: “no se encontró el dato en la lista”.

Fin

Búsqueda Binaria.

El algoritmo de búsqueda binaria elimina de la búsqueda la mitad de los elementos que quedan en el array después de cada comparación. El array debe estar ordenado previamente,  declaramos las variables inicio y fin con la posición inicial y final del array, en la variable posición almacenamos el valor del centro del array.  En la primera iteración se evalúa si la variable posición coincide con el elemento buscado en ese caso la búsqueda termina y devuelve el resultado. Si el elemento buscado es mayor tomamos el intervalo que va desde el elemento central al final, en caso contrario, tomamos el intervalo que va desde el elemento central hasta el principio del intervalo.

Implementación:

//Implementacion recursiva

//Uso: binSearch(vector,0,vector.lenth-1,dato)

Static int binSearch

(double v[]; int izq, int der, doublé buscado)

{

  int centro = (izq+der)/2;

  If (izq>der)

    return -1;

  else if (buscado==v[centro])

    return centro;

  else if (buscando<v[centro])

    return binSearch(v, izq, centro-1, buscado);

  else

    return binSearch(v, centro+1, der, buscado);

}

Static int binSearch (double v[], double buscado)

{

      int izq = 0;

      int der = v.lenth-1;

      int centro = (izq+der)/2;

While ((izq<der) && (v[centro] ¡=buscado))

{

       If (buscado<v[centro])

             der = centro –  1;

       else

             izq  = centro --  1;

       centro =  (izq+der)/2;

}

If  (izq>der)

       return -1;

else

       return centro;

}

Búsqueda por transformación de llaves.

Función  Hash.

La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas.

Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un registro, archivo, documento, etc.

Ventajas:

• Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar.

• Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones.

•  No se requiere almacenamiento adicional para los índices.

 Desventajas:

•  No pueden usarse registros de longitud variable.

•  El archivo no está clasificado.

•  No permite llaves repetidas.

• Solo permite acceso por una sola llave.

 FUNCIONES EN HASH MÁS COMUNES:

•  Residuo de la división: Dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).

•  Medio del cuadrado: La llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa.

• Pliegue: En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales (excepto la última) tiene el mismo número de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa.

OPERACIONES BASICAS:

• Inserción.

•  Búsqueda.

•  Eliminar.

Implementación:

import java.util.*;

public class hash {

public static void main (String args[]) throws Exception

 {

Hashtable hash = new Hashtable(10,10);

for (int i = 0; i <= 100; i++)

{

Integer entero = new Integer ( i );

hash.put( entero, "Numero : " + i);

}

for (Enumeration e = hash.keys(); e.hasMoreElements();)

{

 System.out.println (hash.get(e.nextElement()));

}

}

Colisiones.

Cuando la función hash obtiene una misma dirección para dos claves diferentes, se está ante una colisión.

Algunos métodos más utilizados para resolver colisiones son los siguientes:

•  Reasignación

•  Arreglos anidados

•  Áreas de desborde

Reasignación:

Existen varios métodos que trabajan bajo el principio de comparación y  reasignación de elementos. Se analizaran tres de ellos:

•  Prueba lineal

•  Prueba cuadrática

• Doble dirección hash

a)  Prueba lineal

Consiste en que una vez detectada la colisión se debe de recorrer el arreglo secuencialmente a partir del punto de colisión, buscando al elemento. El proceso de búsqueda concluye cuando el elemento es hallado, o bien cuando se encuentra una posición vacía. Se trata al arreglo como a una estructura circular: el siguiente elemento después del último es el primero. 

b)  Prueba Cuadrática

 Este método es similar al de la prueba lineal. La diferencia consiste en que en el cuadrático las direcciones alternativas se generan como D + 1, D + 4, D + 9,

.D + i² en vez de D + 1, D + 2,..., D + i. Esta variación permite una mejor distribución de las claves colisionadas.

c)  Doble dirección hash

Consiste en que una vez detectada la colisión se debe generar otra dirección aplicando la función hash a la dirección previamente obtenida. El proceso se detiene cuando el elemento es hallado, o bien cuando se encuentra una posición vacía.

La función hash que se aplique a las direcciones puede o no ser la misma que originalmente se aplicó a la clave. No existe una regla que permita decidir cual será la mejor función a emplear en el cálculo de las sucesivas direcciones.