4

Alguien me puede ayudar a hacer un array de 10 números desordenados pedidos por el usuario, luego ordenarlos con el ordenamiento por selección, posteriormente pedir un numero al usuario para después proceder a buscarlo en el array y utilizar la búsqueda binaria para determinar si existe o no. El codigo ya pide los numeros que llevara el array, tambien ya los ordena de menor a mayor, lo unico que falta es poder realizar la busqueda binaria.

#include<stdio.h>
#include<conio.h>
#include<string.h>

int main(){
    int matriz1[10],filas,columnas,i,j,x,dato,y,aux,min,a,inf,sup,mitad;
    char band='F';

    printf("\t\t\t\tNUMEROS DESORDENADOS\n\n");
    printf("digite la cantidad de numeros a ingresar\n");
    scanf("%i",&filas);

    printf("\n\n");
    if (filas>10){
        printf("La cantidad tiene que ser menor a 10");
    }
    else {
        for(i=0;i<filas;i++){
            printf("Digite un numero matriz[%i]",i+1);
            scanf("%i",&matriz1[i]);
        }
    }

    for(i=0;i<filas;i++){
        min=i;
        for(j=i+1;j<filas;j++){
            if(matriz1[j] < matriz1[min]){
                min = j;
            }
        }
        aux=matriz1[i];
        matriz1[i]=matriz1[min];
        matriz1[min]=aux;
    }

    printf("ASCENDENTE\n");
    for(i=0;i<filas;i++){
        printf("%i ",matriz1[i]);
    }

    printf("\t\t\t\tBUSQUEDA BINARIA\n\n");
    printf("Digite el numero que desea buscar\n");
    scanf("%i",dato);

    inf=0;
    sup=filas;

    while (inf<=sup)
    {
        mitad=(inf+sup)/2;
        if (matriz1[mitad]==dato)
        {
            printf("dato %d encontrado posicion %d",dato,mitad);
            break;  
        }
        if (matriz1[mitad]>dato)
        {
            sup=mitad;
            mitad=(inf+sup)/2;
        }
        if (matriz1[mitad]<dato)
        {
            inf=mitad;
            mitad=(inf+sup)/2;
        }
    }

    getch();
    return 0;
}

2 respuestas 2

2

Primero, tienes un error que considero simplemente tipográfico, porque en el resto lo hace bien en:

scanf("%i", dato);

debe ser:

scanf("%i", &dato);
            ^
            ^

En cuanto al algoritmo, sup no debe ser igual a filas, sino a filas - 1 que es el último índice válido del array.

Los pasos serían los siguientes:

  1. En cada iteración, calculamos la posición media entre ambos límites:

    (indice superior + indice inferior) / 2
    
  2. Si el dado es igual al de la posición media terminamos, lo hemos encontrado.

  3. Si el dato es mayor que el valor medio se cambia el límite inferior para que sea la mitad más uno.

  4. Si el dato es menor que el valor medio se cambia el límite superior para que sea la mitad menos uno.

  5. Si llegamos al punto en el que el límite inferior es mayor que el superior, el elemento no está en el array ordenado y terminamos.

El principal error está en los puntos 3 y 4. El índice mitad ya ha sido comprobado, por lo que no debe formar parte del siguiente rebanado, el problema más importante con ésto es hacer inf = mitad; en vez de inf = mitad + 1; en el punto 3. Ésto ocasiona que termines con ciclos infinitos, por ejemplo:

  • Partimos de:

    dato = 8
    array = [4, 5, 6]
    
  • 1ª. Iteración

    inf = 0
    sup = 3
    mitad = (3 + 0) / 2 = 1
    Como array[1] < 8:
        inf = mitad = 1
    
  • 2ª. Iteración

    inf = 1
    sup = 3
    mitad = (3 + 1) / 2 =  2
    Como array[2] < 8:
        inf = mitad = 2
    
  • 3ª. Iteración

    inf = 2
    sup = 3
    mitad = (3 + 2) / 2 = 2
    Como array[2] < 8:
       inf = mitad = 2
    
  • Volvemos a estar como en la 2ª iteración, de aquí ya no sales...

Debería ser algo así:

inf = 0;
sup = filas - 1;

while (inf <= sup)
{
    mitad = (sup + inf) / 2;
    if (matriz1[mitad] == dato)
    {
        printf("Dato %d encontrado posicion %d", dato, mitad);
        break;
    }
    else if (matriz1[mitad] > dato)
        sup = mitad - 1;
    else
        inf = mitad + 1;
}

if (inf > sup)
    printf("Dato %d no encontrado", dato);

Por eficiencia, en vez de encadenar if cuando sabes que de cumplirse uno el otro no va a ser cierto nunca (por tanto no tiene sentido que se evalúe siquiera), usa else if - else. Con if encadenados todas las condiciones se evalúan, con else if si alguna del bloque anteriormente se evaluó como cierta el resto ya no serán evaluadas.

El cálculo de mitad en los condicionales, aunque no afecta al algoritmo, es innecesario también, dado que en la siguiente iteración se recalcula al inicio de la misma.

2
  • 1
    ¿Por qué el calculo de la posición media debe ser así inf + ((sup - inf) / 2)? La forma como lo hace el OP es correcto.
    – MrDave1999
    Commented el 29 abr. 2020 a las 14:29
  • 1
    @MrDave1999 tienes razón, lo que pretendía hacer con la lista era enumerar los pasos del algoritmo y marcar en negrita los puntos erróneos (los condicionales básicamente), al tratarse de índices creo que es más intuitivo de entender la forma en la que lo expresaba, aunque es más ineficiente al implementarlo (una operación más)... En fin, creo que lo lie todo un poco, es lo que tiene contestar a una pregunta antes de que el café haga efecto... La he editado, he dejado esa parte como la tenía el op para no confundir y he tratado de explicar mejor el error. Gracias por el comentario y un saludo.
    – FJSevilla
    Commented el 29 abr. 2020 a las 15:45
0

Lo habitual en la búsqueda binaria es redactar una función recursiva:

int busqueda_binaria(int valor, int *numeros, int inicio, int fin)
{
    if (valor == numeros[inicio])
        return inicio;

    int centro = inicio + ((fin - inicio) / 2);

    if (valor <= numeros[centro])
        return busqueda_binaria(valor, numeros, inicio, centro);
    else
        return busqueda_binaria(valor, numeros, centro + 1, fin);
}

Puedes ver el código funcionando en Try it online!.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.