BUSQUEDA BINARIA

BUSQUEDA BINARIA

Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmo más eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer.

Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado, sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí.

Este método permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño. La sintaxis expresada de forma genérica para realizar este método es la siguiente:

Int BinarySearch ([ ] m. tipo clave)

Donde m representa la matriz, clave es el valor que se desea buscar del mismo tipo que los elementos de la matriz, tipo es cualquier tipo de datos de los siguientes: objet, string, byte, char, short, int, long, flota, double, etc.

La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:

int vector[10] = {2,4,6,8,10,12,14,16,18,20};

La clave que queremos buscar es 6. El algoritmo funciona de la siguiente manera

1. Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.

2. Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.

3. Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.

4. Si son distintos, evaluamos si vector[Icentro] es mayor o menor que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector[0…5] ya puede descartarse.

5. Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2.

CODIGO

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

namespace busquedabinaria

{

public partial class Form1 : Form

...