Busqueda Binaria – C Sharp

Hace unos dí­as y poní­a un ejemplo acerca de búsquedas lineales en arreglos, ésta vez hablaremos acerca de las búsquedas lineales, un método mucho más rápido para buscar elementos.

¿Cómo funciona este método? Para poder aplicar éste método de búsqueda es necesario que el arreglo esté ordenado; posteriormente, se aplica el siguiente algoritmo: se ubica el elemento de la mitad del arreglo, entonces, si el número que se está buscando dentro del arreglo es menor al número de la mitad, se busca el número de la mitad entre el inicio del y la mitad del mismo, y así­ hasta encontrar el elemento deseado.

Por ejemplo, suponiendo que tenemos un arreglo con los siguientes valores:

2, 4, 5 , 6, 8, 9, 10, 12, 24, 34, 46, 56, 60, 67, 78, 89, 90

…y queremos buscar el valor 10; tenemos que, el elemento de la mitad contiene el valor 24. Puesto que 24 > 10, buscamos el valor intermedio entre el principio del arreglo y la mitad del mismo, esto es 8. Puesto que 8 < 10, buscamos el valor intermedio entre 8 y la mitad del arreglo (24), esto es 10. Así­, con tan solo 3 bucles, hemos conseguido el valor buscado.

Vamos con el código del programa, que nos sacará de toda duda:

using System;
using System.Drawing;
using System.Windows.Forms;
public class EjemploBusquedaBinaria : Form
{
  private Label labelSolicitar;
  private TextBox cajaEntrada;
  private Label labelResultado;
  private Label labelMostrar;
  private Label labelSalida;
  private Button botonBuscar;
  int[] a = { 0, 2, 4, 6, 8, 10, 12, 14, 16,
              18, 20, 22, 24, 26, 28 };
  public EjemploBusquedaBinaria(){
     InitializeComponent();
  }
  private void InitializeComponent() {
     this.labelMostrar = new Label();
     this.labelResultado = new Label();
     this.cajaEntrada = new TextBox();
     this.labelSolicitar = new Label();
     this.botonBuscar = new Button();
     this.labelSalida = new Label();
     this.SuspendLayout();
     //
     // labelMostrar
     //
     this.labelMostrar.Location = new System.Drawing.Point(261, 8);
     this.labelMostrar.Name = "labelMostrar";
     this.labelMostrar.Size = new System.Drawing.Size(152, 20);
     this.labelMostrar.TabIndex = 3;
     //
     // labelResultado
     //
     this.labelResultado.Location = new System.Drawing.Point(213, 8);
     this.labelResultado.Name = "labelResultado";
     this.labelResultado.Size = new System.Drawing.Size(50, 16);
     this.labelResultado.TabIndex = 2;
     this.labelResultado.Text = "Resultado:";
     //
     // cajaEntrada
     //
     this.cajaEntrada.Location = new System.Drawing.Point(99, 8);
     this.cajaEntrada.Name = "cajaEntrada";
     this.cajaEntrada.TabIndex = 1;
     this.cajaEntrada.Text = "";
     //
     // labelSolicitar
     //
     this.labelSolicitar.Location = new System.Drawing.Point(27, 8);
     this.labelSolicitar.Name = "labelSolicitar";
     this.labelSolicitar.Size = new System.Drawing.Size(56, 16);
     this.labelSolicitar.TabIndex = 0;
     this.labelSolicitar.Text = "Digite el dato";
     //
     // botonBuscar
     //
     this.botonBuscar.Location = new System.Drawing.Point(152, 40);
     this.botonBuscar.Name = "botonBuscar";
     this.botonBuscar.Size = new System.Drawing.Size(136, 24);
     this.botonBuscar.TabIndex = 5;
     this.botonBuscar.Text = "Buscar dato";
     this.botonBuscar.Click += new System.EventHandler(this.botonBuscar_Click);
     //
     // labelSalida
     //
     this.labelSalida.Font = new System.Drawing.Font("Courier New", 8.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((System.Byte)(0)));
     this.labelSalida.Location = new System.Drawing.Point(10, 80);
     this.labelSalida.Name = "labelSalida";
     this.labelSalida.Size = new System.Drawing.Size(420, 72);
     this.labelSalida.TabIndex = 4;
     //
     // EjemploBusquedaBinaria
     //
     this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
     this.ClientSize = new System.Drawing.Size(440, 157);
     this.Controls.AddRange(new Control[] {
            this.botonBuscar,
            this.labelSalida,
            this.labelMostrar,
            this.labelResultado,
            this.cajaEntrada,
            this.labelSolicitar});
     this.Name = "EjemploBusquedaBinaria";
     this.Text = "Busqueda Binaria";
     this.ResumeLayout(false);
  }
  static void Main() {
     Application.Run( new EjemploBusquedaBinaria() );
  }
  private void botonBuscar_Click( object sender,
     System.EventArgs e )
  {
     int valorBuscar = Int32.Parse( cajaEntrada.Text );
     // iniciar los datos de salida
     labelSalida.Text = "Portions of array searched\n";
     // realizar busqueda binaria
     int elemento = Buscar( a, valorBuscar );
     if ( elemento != -1 )
        labelMostrar.Text = "Valor encontrado en indice " +
           elemento;
     else
        labelMostrar.Text = "Valor no encontrado";
  } // fin botonBuscar_Click
  // buscar mediante metodo binario
  public int Buscar( int[] array, int dato ) {
     int bajo = 0;
     int alto = array.Length - 1;
     int medio;
     while ( bajo <= alto ) {
        medio = ( bajo + alto ) / 2;
        // el siguiente método nos muestra la porción del
        // arreglo donde se está llevando a cabo la busqueda
        // del dato en cada iteración del bucle
        construirSalida( a, bajo, medio, alto );
        if ( dato == array[ medio ] )   // si se encuentra el valor
           return medio;
        else if ( dato < array[ medio ] )
           alto = medio - 1;   // buscar en la mitad más baja
        else
           bajo = medio + 1;   // buscar en la mitad más alta
     } // fin de la busqueda binaria
     return -1;  // dato no encontrado
  } // fin del metodo Buscar
  public void construirSalida(
     int[] array, int bajo, int mid, int alto ) {
     for ( int i = 0; i < array.Length; i++ ) {
        if ( i < bajo || i > alto )
           labelSalida.Text += "    ";
        // marcar el elemento de la mitad en la salida
        else if ( i == mid )
           labelSalida.Text +=
              array[ i ].ToString( "00" ) + "* ";
        else
           labelSalida.Text +=
              array[ i ].ToString( "00" ) + "  ";
     }
     labelSalida.Text += "\n";
  } // fin de construirSalida
} // fin de la clase EjemploBusquedaBinaria

Descargar código fuente

17 Comentarios | deja el tuyo