2

estoy tratando de utilizar búsqueda binaria en un array ordenado, lo que quiero hacer es buscar un número en el array, pero si no lo encuentra que me imprima el numero que mas se acerca por la derecha y por la izquierda, por ejemplo, si tengo el siguiente allego: 1 3 4 5. Y quiero buscar el número 2, que me imprima, izquierda= 1, derecha =3. Solo estoy atorado en esa parte, les dejo mi código para que lo puedan revisar:

#include <stdio.h>
#include <stdlib.h>

int ordenar(const void *p, const void *q);

int main()
{
    int n,inf,sup,mitad,dato,i; 
    long long arreglo[100000]={0};
    char band='F';
    long int m;
    int a=0,b=0;
    
    scanf("%d",&n);
    
    
    for( int  i = 0; i < n; i++ ) {
        scanf("%d",&arreglo[i]); 
        
    }
    
    //Ordenamiento
    
    qsort(arreglo,n,sizeof arreglo[0],&ordenar);
        dato = 2;
        int cero = 0;
    
    //Algoritmo de la Busqueda Binaria
    inf=0;
    sup=n;
    i=0;
    while((inf<=sup)&&(i<n)){
        mitad = (inf+sup)/2;
        if(arreglo[mitad] == dato){
            band='V';
            break;
        }
        if(arreglo[mitad]>dato){
            sup = mitad;
            mitad = (inf+sup)/2;
            a=(inf+sup)/2;
        printf("%d",arreglo[a]);    
        }
        if(arreglo[mitad]<dato){
            inf = mitad;    
                
            mitad = (inf+sup)/2;
        
        }
        i++;
    
    }
            
    if(band == 'V'){
        printf("%d ",cero);
    }
    else{
    //  int resultado=b-a;
    //  printf("%d",resultado);
    }
  
    return 0;  
    }
}
   

1 respuesta 1

0

Tú código realmente funciona. Cuando acaba el algoritmo, los valores (en caso de no hallarse el número dentro del array) izquierda y derecha corresponden a arreglo[inf] y arreglo[sup] respectivamente. Puedes añadir una mejora como es que cuando los valores inf y mitad o sup y mitad sean iguales se salga del bucle mediante un break.

Te dejo tu código con unas mínimas modificaciones y alguna información que se verá en pantalla por si te sirve de guía.

#include <stdio.h>
#include <stdlib.h>

int ordenar(const void *_a, const void *_b)
{

    int *a, *b;

    a = (int *) _a;
    b = (int *) _b;

    return (*a - *b);
}

int main()
{
    int n,inf,sup,mitad,dato;
    long long arreglo[100000]= {0};
    char band='F';

    scanf("%d",&n);

    for(int  i = 0; i < n; i++ )
    {
        scanf("%d",&arreglo[i]);

    }
    //Ordenamiento
    qsort(arreglo,n,sizeof arreglo[0],&ordenar);
    dato = 5;
    int cero = 0;

    for (int i=0; i<n; i++)
    {
        printf("%d",arreglo[i]);
    }

    //Algoritmo de la Busqueda Binaria
    inf=0;
    sup=n;
    int i=0;
    mitad = (inf+sup)/2;
    while((inf<sup)&&(i<n))
    {
        if(arreglo[mitad] == dato)
        {
            band='V';
            break;
        }
        if(arreglo[mitad]>dato)
        {
            printf("%s","\nestoy entre : ");
            printf("%d",arreglo[inf]);
            printf("%s"," y ");
            printf("%d",arreglo[mitad]);
            sup = mitad;
            mitad = (inf+sup)/2;
            if (sup==mitad)
            {

                break;
            }
        }
        else if(arreglo[mitad]<dato)
        {
            printf("%s","\nestoy entre : ");
            printf("%d",arreglo[inf]);
            printf("%s"," y ");
            printf("%d",arreglo[mitad]);
            inf = mitad;
            mitad = (inf+sup)/2;
            if (inf==mitad)
            {
                break;
            }
        }
        i++;
    }

    if(band == 'V')
    {
        printf("%s%d%s%d ","\nEncontrado el nº ",arreglo[mitad]," en la posicion ",mitad);
    }
    else
    {
        printf("%s%d","\nIzquierda: ",arreglo[inf]);
        printf("%s%d","\nDerecha: ",arreglo[sup]);
    }

    return 0;
}

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.