[C] algoritmo di ricerca dicotomica su array ordinato

di il
4 risposte

[C] algoritmo di ricerca dicotomica su array ordinato

Cioa a tutti, ho scritto questo programma per la ricerca dicotomica.
per compilare lo compila senza errori ma quando lo lancio non fa nulla..

presumo che l' errore sia nel ciclo iterazione del while... forse un errore con gli indici ma non riesco a capire dove. Qualcuno può aiutarmi?
#include <stdio.h>
#include <stdlib.h>
#define N 12
int main()
{
    int v[N]= {1,2,3,5,6,8,9,10,13,22,44,56};
    int i,j,medio,flag,cerca=5; //lunghezza=N
    i=0;
    j=N-1;     //<----messo -1 {perchè l' indice dell' ultimo elemento è dimensione vettore(=N) -1}
    flag=0;

    while(j>i || !flag)   //<------ messo ||  visto che deve uscire dal ciclo se j supera i o se trovo !flag
    {
        if((j-i)%2==0)
            medio=(j-i)/2;

        else
            medio=((j-i-1)/2);
            //printf("%d\n",medio);

        if(cerca==v[medio])
            flag=1;
        else if(cerca<v[medio])
            j=medio-1;
        else if(cerca>v[medio])
            i=medio+1;
    }

    if(flag==0)
    printf("non trovato");
    else if(flag==1)
    printf("TROVATO");
    return 0;


}

4 Risposte

  • Re: [C] algoritmo di ricerca dicotomica su array ordinato

    Giusto un paio di errori
    
    #include <stdio.h>
    #include <stdlib.h>
    #define N 12
    
    int main(void)
    {
    	int v[N] = { 1, 2, 3, 5, 6, 8, 9, 10, 13, 22, 44, 56 };
    	int i, j, medio, flag, cerca = 5; //lunghezza=N
    	i = 0;
    	j = N - 1;     //<----messo -1 {perchè l' indice dell' ultimo elemento è dimensione vettore(=N) -1}
    	flag = 0;
    	char c;
    
    	while (i<=j && !flag)   //<------ messo ||  visto che deve uscire dal ciclo se j supera i o se trovo !flag
    	{
    
    		medio = (i+j) / 2;
    
    		if (cerca == v[medio])
    			flag = 1;
    		else if (cerca < v[medio])
    			j = medio - 1;
    		else
    			i = medio + 1;
    	}
    
    	if (flag == 0)
    		printf("non trovato\n");
    	else if (flag == 1)
    		printf("TROVATO\n");
    	return 0;
    
    }
    
    Come puoi vedere:
    - la condizione del while è doppiamente sbagliata, ovvero devi controllare che i due indici si "sorpassino" E che il dato non sia stato trovato
    - l'indice lo puoi calcolare contando sulla divisione intera senza controlla se il numero è pari o dispari.
    - l'ultimo else if è inutile in quanto gli altri casi li hai già scartati con i due precedenti.
  • Re: [C] algoritmo di ricerca dicotomica su array ordinato

    Hai ragione! sono stato a preoccuparmi troppo su quel pari/dispari convinto fosse utile quando potevo benissimo farne a meno.
    ora funziona, Grazie mille.
  • Re: [C] algoritmo di ricerca dicotomica su array ordinato

    Anche l'ultima if è da correggere
  • Re: [C] algoritmo di ricerca dicotomica su array ordinato

    oregon ha scritto:


    Anche l'ultima if è da correggere
    Mi è sfuggito qualcosa?
Devi accedere o registrarti per scrivere nel forum
4 risposte