busqueda binaria

Búsqueda binaria
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
La búsqueda binaria es un algoritmo de búsqueda.
Para realizarla, es necesario contar con un array o vectorordenado. Luego tomamos un elemento central, normalmente el elemento que se encuentra a la mitad del arreglo, y lo comparamos con el elemento buscado. Si el elemento buscado es menor, tomamos el intervaloque va desde el elemento central al principio, en caso contrario, tomamos el intervalo que va desde el elemento central hasta el final del intervalo.
Procedemos de esta manera con intervalos cadavez menores hasta que lleguemos a un intervalo indivisible, en cuyo caso el elemento no está en el vector, o el elemento central sea nuestro elemento.
De esta forma la complejidad computacional sereduce a O(ln N).
El algoritmo se puede implementar con o sin recursión, a continuación se presenta una versión iterativa en Lenguaje C:



Int Bbin(int dato,int n){
int inicio,final,medio;inicio = 0;
final = n-1;
while (inicio array[medio])
inicio = medio+1;
else
final = medio-1;
}
return -1;
}









Y aquímostramos una versión recursiva del mismo algoritmo:

int bbin(int dato, int *v, int inicio, int final)
{
int medio = floor( (final + inicio) / 2 );
if ( inicio > final ) return -1;if( dato == v[medio] )
return medio;
else if( dato < v[medio] )
return bbin(dato, v, inicio, medio-1);
else if( dato > v[medio] )return bbin(dato, v, medio+1, final);
}


Versión Iterativa en WinPseudo V1.4

INICIO Programa11 - Busqueda Binaria
VAR
NUMERICO i
NUMERICO f
NUMERICO m
VECTORA[20]
NUMERICO enc
NUMERICO Valor
FIN-VAR

IMPRIMIR NL, "Aguarde. Asignando 20 Valores al Vector...", NL

i = 0
MIENTRAS (i < 20)
A[i] = i + 10
i = i...