Método de Búsqueda

Método de Búsqueda Binaria

la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra del primer apellido o de la palabra que busca. Se puede tener suerte

y acertar con la página correcta; pero, normalmente, no será así y se mueve el lector a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con «J» y se está en la «L» se mueve uno hacia atrás. El proceso continúa hasta que se encuentra la página buscada o hasta que se descubre que la palabra no está en la lista.

Técnica del Método de Búsqueda:

Se aplica en la búsqueda en una lista ordenada. Se sitúa la lectura en el centro de la lista y se comprueba si la clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sigue la búsqueda uno en la mitad inferior o superior del elemento central de la lista. En general, si los datos de la lista están ordenados se puede utilizar esa información para acortar el tiempo de búsqueda.

Ejemplo


Se desea buscar el elemento 225 y ver si se encuentra en el conjunto de datos siguiente:

a[0]      a[1]      a[2]     a[3]      a[4]      a[5]       a[6]      a[7]
13         44         75      100      120       275       325       510


El punto central de la lista es el elemento a[3] (100). El valor que se busca es 225, mayor que 100; por consiguiente, la búsqueda continúa en la mitad superior del conjunto de datos de la lista, es decir, en la sublista,

a[4] a[5] a[6] a[7]
120 275 325 510

Ahora el elemento mitad de esta sublista a[5] (275). El valor buscado, 225, es menor que 275 y, por consiguiente, la búsqueda continúa en la mitad inferior del conjunto de datos de la lista actual; es decir, en la sublista de un único elemento:

a[4]
120

El elemento mitad de esta sublista es el propio elemento a[4] (120). Al ser 225 mayor que 120, la búsqueda debe continuar en una sublista vacía. Se concluye indicando que no se ha encontrado la clave en la lista.

Codificación de Método de Búsqueda Binaria 

int busq_bin(int a[], int n, int nx)

{

int central,bajo,alto,valorCentral;

bajo=1;

alto=n-1;

while(bajo<=alto)

     {

     central=(bajo+alto)/2;

     valorCentral=a[central];

     if(nx==valorCentral)

       return(central);

     else if(nx<valorCentral)

       alto=central-1;

     else

       bajo=central+1;

     }

     return-1;

}

Prueba de Escritorio: