Vale, a ver. Recuperando un código mio de Java, lo he porteado a C y lo he integrado en tu código.
No estoy muy ducho en C, lo mio es Java. Pero lo he compilado y funciona.
He modificado la constante dimension a valor 10, para que la busqueda sea un poco más larga e interesante.
El resto de código apenas lo he modificado, solo la parte donde hacemos la busqueda.
He cambiado el bucle while, por un do ..while.
Viene a ser lo mismo en realidad, pero para este ejercicio queda mejor en mi opinion.
Tambien añado un booleano para controlar si hemos encontrado el valor a buscar o no.
Es mejor informar de si lo hemos encontrado o no cuando el bucle haya terminado de buscar.
El bucle puede terminar por haberlo encontrado o porque ya no quedan números para seguir comparando. Esta variable booleana nos servirá para saber cuál de las dos posibilidades ha ocurrido.
He puesto una linea que empieza por "Debug Info:" para que informe por pantalla que posicion del vector está consultando en cada momento.
No es necesaria para resolver el problema, pero es interesante ver como se va recalculando el valor de central. Sobre todo si aumentamos aún más la dimension del vector.
En fin, lo realmente interesante y algo difícil, es la parte en como recalculamos los valores de alto, bajo y central según si el numero es mayor o menor.
if (valor < arreglo[central])//Verificamos si el valor introducido por el usuario, es menor al de la variable en central//
{
//Valor es menor, hay que recalcular primero la variable alto y luego central
alto = central - 1;
central = (alto - bajo) / 2 + bajo;
}
else
{
//Valor es mayor, hay que recalcular primero la variable bajo y luego central
bajo = central + 1;
central = (alto - bajo) / 2 + bajo;
}
Las dos líneas que pusiste tú, se acercaban bastante a la solución, pero esta es en realidad un poquito más complicada.
No parece evidente al principio, sobre todo al trabajar con un vector de solo dimension 3, pero el resultado de dividir por 2 la resta de alto - bajo, hay que sumarsela despues a bajo
Supón un vector de dimension 10. REsulta que
bajo = 0
alto = 9
central = 4 --> (9/2 = 4.5 --> Al pasar a int la posicion es 4 )
El numero no coincide y es mayor, así que tenemos que recalcular la variable bajo y central
bajo = central + 1 -- > 5
alto = 9 (este no cambia)
central = (alto - bajo) / 2 --> (9 - 5) / 2 --> 2
¿Como que un 2 ? Esto no es correcto, debemos preguntar por una posicion mayor que 4 , y 2 es menor ....
Claro, por eso digo que el resultado de este cálculo, hay que sumárselo siempre a bajo.
Atentos:
central = (alto - bajo) / 2 + bajo--> (9 - 5) / 2 + 5 --> 7
Ahora sí!!! Hemos conseguido el 7, que si es mayor que la posicion 4 por la cuál habiamos preguntado anteriormente.
No se si con esta explicación ha quedado claro, si haces tu mismo a lapiz y papel una simulación de estos cálculos cada vez que el bucle se repite buscando el número, quizás lo entiendas mejor.
En fin, te pongo abajo el código completo. Si lo compilas debería funcionar.
Importante, esto que yo he hecho es una búsqueda dicotómica, pero no es recursiva
Si consigues que te quede claro como funciona esta búsqueda, prueba a transformarlo tú en una búsqueda recursiva.
Suponiendo que entendemos lo mismo "por recursiva". Es decir, cuando hablamos "de recursividad", hablamos de una función que se llama a si misma internamente varias veces proporcionandose distintos valores para sus parametros.
Por eso dije al principio que en ese caso, tendrás que escribir una función que se encargue de hacer busquedas dicotómicas y que se llame a si misma hasta encontrar el número a buscar o hasta que no queden numeros por comprobar.
Aqui mi código completo:
#include <stdio.h>
#include <stdlib.h>
#define dimension 10
int main()
{
int indice, j;
int pos_menor, alto, central, bajo;
float arreglo[dimension];
float menor, AUX;
float valor;
/*Leer Vector*/
for (indice = 0; indice<dimension; indice++)
{
printf("arreglo[%i]= ", indice);//Ingresa los valores para el arreglo//
scanf("%f", &arreglo[indice]);
}
//Orden por Selección//
for (indice = 0; indice<dimension; indice++)
{
menor = arreglo[indice];//Asignamos el contenido del arreglo a la variable menor//
pos_menor = indice;//Asignamos el valor del indice del arreglo a la variable pos_menor/
for (j = indice + 1; j<dimension; j++)//Ciclo iterativo para ordenar por selección//
{
if (menor>arreglo[j])// Sentencia if para evaluar que la variable menor sea mayor ha arreglo//
{
menor = arreglo[j];//Se asigna el contenido del arreglo en la posición j, a la variable menor//
pos_menor = j;//Asignamos el contenido o valor de j a la variable pos_menor//
}
}
//Intecambiar//
AUX = arreglo[indice];//Se usa para almacenar el contenido del arreglo, en la posicion indicada por el indice//
arreglo[indice] = arreglo[pos_menor];//Igualamos el contenido de los indices del arreglo con los de arreglo pos_menor//
arreglo[pos_menor] = AUX;//Se asignan a la variable auxiliar los valores anteriores//
}
//Imprimir o mostrar el Vector en orden ascendente//
for (indice = 0; indice<dimension; indice++)
{
printf("arreglo[%i]=%f\n", indice, arreglo[indice]); //Muestra el vector ordenado, en orden ascendente, %i indica numeros enteros//
}
printf("\n Que valor desea buscar? ");//indicamos al usuario que diga cual valor desea buscar//
scanf("%f", &valor);//capturamos el valor anterior anterior en la variable valor//
bajo = 0;//asignamos el valor 0 a la variable bajo//
alto = dimension - 1;//restamos 1 a la variable dimension, el resultado lo asignamos a la variable alto//
central = alto / 2;//sumanos los contenidos de alto y bajo lo dividimos entre 2, el resultado lo asignamos a la variable central//
//Busqueda Binaria
bool encontrado = false;
do
{
printf("--Debug info: Consultando Posicion --> %i\n", central);
if (valor == arreglo[central])
{
printf("Encontrado!!\n");
encontrado = true;
}
else
{
if (valor < arreglo[central])//Verificamos si el valor introducido por el usuario, es menor al de la variable en central//
{
//Valor es menor, hay que recalcular primero la variable alto y luego central
alto = central - 1;
central = (alto - bajo) / 2 + bajo;
}
else
{
//Valor es mayor, hay que recalcular primero la variable bajo y luego central
bajo = central + 1;
central = (alto - bajo) / 2 + bajo;
}
}
} while ((bajo <= alto) && !encontrado);
//Consultamos si lo hemos encontrado o no
if (encontrado)
printf("El valor se encuentra en la posicion:%i", central);
else
printf("Valor no encontrado");
printf("\n");
system("PAUSE");
return 0;
}