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;
}
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;
}
}