Búsqueda binaria

Si el número de elementos es grande, el algoritmo de búsqueda secuencial es muy lento. Pensamos que tuviéramos que consultar un nombre en la guía telefónica de Barcelona con más de un millón de abonados, según el nombre que buscáramos la consulta sería eterna. Naturalmente una persona cuando hace esta búsqueda no utiliza nunca este método secuencial, sino un método basado en en la división sucesiva del espacio ocupado en sucesivas mitades, hasta encontrar el elemento buscado.

Si los datos están clasificados en un determinado orden, el método citado anteriormente se llama búsqueda binaria.

La búsqueda comienza examinando el elemento central, si éste es el elemento buscado ya hemos terminado. De lo contrario se determina si el elemento buscado está en la primera parte o en la segunda parte de la lista y a continuación se repite este proceso, utilizando el elemento central de esta sublista.

var primero, ultimo, central: entero; encontrado: booleano;
encontrado :=falso;
primero :=1;
ultimo := N;
Mientras (primero <= ultimo) y (no encontrado) hacer
  central := (primero + ultimo) / 2 ;
  si v[central] = x entonces
encontrado :=cierto ;
  sino
si v[central] > x semillas
  ultimo := central – 1;
  sino
  primero :=central + 1;
  fsi
  fsi
  fmientras

 

Pin It