Algoritmos de Búsqueda

Algoritmos de Búsqueda

 

Secuencial

 

La forma más simple de búsqueda es la búsqueda secuencial. Esta búsqueda es aplicable a una tabla “organizada”, ya sea como un arreglo o como una lista ligada. Supongamos que x es un arreglo de N llaves, de x(0) a x(N-1) y y el termino que deseamos encontrar en el arreglo, el algoritmo de búsqueda queda como:

 

  static public int busqueda_secuencial(double x[], double y, int N)

  {

    int i;

   

    for(i=0; i<N; i++)

      if(x[i] == y) return i;

   

    return -1;   

  }

 

Búsqueda Binaria

 

El método de búsqueda más eficiente en una tabla secuencial sin usar índices o tablas auxiliares es el método de búsqueda binaria. Básicamente, se compara el argumento con la llave del elemento medio de la tabla. Sin son iguales, la búsqueda termina con éxito; en caso contrario, se busca de manera similar en la mitad superior o inferior de la tabla, según sea el caso.

 

  static public int busqueda_binaria(double x[], double y, int N)

  {

    int inicio = 0, fin = N, mitad;

   

    while(inicio <= fin)

    {

      mitad = (fin + inicio)/2;

 

      if(y == x[mitad]) return mitad;

     

      if(y < x[mitad]) fin = mitad -1;

      else inicio = mitad + 1;

    }

    return -1;

  }

 

El siguiente código muestra la implementación de ambos y un programa principal para hacer un llamado a cada uno de los métodos de búsqueda antes mencionados.

 

class busqueda

{

  static public void main(String args[])

  {

 

    double x[] = {1,2,4,7, 10, 11, 20, 21, 32};

    int N = 9, i;

    double y = 10;

 

    i = busqueda_secuencial(x, y, N);

    System.out.println("El valor "+ y + " se encuentra en la posicion " + i);

    System.out.println("El valor "+ x[i] + " se encuentra en la posicion "

      + busqueda_binaria(x, y, N));

  }

 

  static public int busqueda_secuencial(double x[], double y, int N)

  {

    int i;

   

    for(i=0; i<N; i++)

      if(x[i] == y) return i;

   

    return -1;   

  }

 

  static public int busqueda_binaria(double x[], double y, int N)

  {

    int inicio = 0, fin = N, mitad;

   

    while(inicio <= fin)

    {

      mitad = (fin + inicio)/2;

 

      if(y == x[mitad]) return mitad;

     

      if(y < x[mitad]) fin = mitad -1;

      else inicio = mitad + 1;

    }

    return -1;

  }  

 

}

 

Regresar.