[C++] Ricerca adattiva

[Il Pazzo]

int ricercaAdattiva(int v[], int n, int x){
	int primo = 0;
	int ultimo = n - 1;
	
    while(ultimo > primo){
		int m = (ultimo + primo) / 2 + 1;
      	int prox = primo + ((ultimo - primo) * ((x - v[primo]) / (v[ultimo] - v[primo])));
		if ((v[prox] > x) && (prox - primo < m)){
			ultimo = prox - 1;
			//prox = (primo + ultimo) / 2;
		}
		else if((v[prox] < x) && (ultimo - prox) < m) {
			primo = prox + 1;
			//prox = (primo + ultimo) / 2;
		}
		else if(v[prox] < x) primo = m + 1;
		else if(v[prox] > x) ultimo = m - 1;
		else primo = m;
    }
	
	if(v[primo] == x) return primo;
	else if(v[ultimo] == x) return ultimo;
	else return -1;
}

Uff... non riesco a corregere il codice.... Su google non trovo nulla forse ha un altro nome questa tipo di ricerca???
Sarebbe una ricerca mezza interpolata e mezza binaria (implementate tutte e due correttamente ma nel momento di metterle insieme... il casino) ....

Grazie per l'aiuto..

[oregon]

Pero' non puoi dire "uff", "il casino" e simili ...

Devi esprimerti tecnicamente e dettagliatamente indicando qual e' il problema (se hai errori, se non funziona ...), con quali dati hai fatto le prove, quali risultati ... da dove hai preso le due parti di codice ...

... insomma, non crederai che con un "uff" si prenda il codice si compili, si corregga e ti si fornisca impiattato pronto da mangiare? Sai quanto tempo si perderebbe? ... Un po' di collaborazione ...

[Il Pazzo]

si scusa.. allora... il codice compila correttamente... parte... non va in loop infinito ne nulla... semplicemente non trova l'elemento.... le 2 parti di codice li ho presi dalle 2 ricerche che ho implementato precedentemente e che funzionano.... ecco i codici:

Ricerca binaria:

int ricercaBinariaIterativa(int v[], int n, int x){
	int primo = 0;
	int ultimo = n - 1;
	
    while(primo <= ultimo){
		int m = (primo + ultimo) / 2;
        if (v[m] == x) return m; // elemento trovato!
        
		if(v[m] < x)
            primo = m + 1;
        else
            ultimo = m - 1;
   }

   return -1;
}

Ricerca Interpolata:

int ricercaInterpolata(int v[], int n, int x){
	int primo = 0;
	int ultimo = n - 1;
	
    while((v[ultimo] >= x) && (v[primo] < x)){
		int m = primo + ((ultimo - primo) * ((x - v[primo]) / (v[ultimo] - v[primo])));
        
		if (v[m] < x) primo = m + 1;
		else if(v[m] > x) ultimo = m - 1;
		else primo = m;
   }
	
	if(v[primo] == x) return primo;
	else return -1;
}

[oregon]

Ok ... così va un po' meglio ... capirai che per dare una mano bisogna avere il maggior numero di informazioni possibili ...

Pero' non capisco ancora secondo quali criteri puoi unire i due algoritmi ... non conosco la "ricerca adattiva" ma avrai qualche documentazione a cui fare riferimento ...

[Il Pazzo]

Ma guarda ti dirò la verità.... Io non conoscevo neanche quella interpolata.... Ste ricerche le ho prese dagli appunti che il prof (Mi devo dare l'esame di algoritmi all'uni) aveva su internet (Ora li ha tolti perchè vuole fare un libro... che sinceramente sconsiglio)....

Allora... il mio prof ha implementato ste 3 ricerche
Binaria, interpolata e adattiva però boh... non funzionava nessuna... le prime due sono riuscito a correggerle (quella interpolata trova l'elemento ma onestamente credo sia ancora sbagliata perchè debuggando ho notare che scorre tutto il vettore)... quest'ultima ricerca... quella adattiva.. secondo gli appunti del prof... diminuirebbe il vettore o di metà (usando l'algoritmo binario) o in una parte ancora più piccola(l'algoritmo interpolato o come si dice)... cioè mi speigo meglio.. se ad esempio con la ricerca interpolata il vettore vine diviso in 3/4 e 1/4 e l'elemento si trova nella parte più grande allora viene utilizzata la ricerca bianaria.. altrimenti quella interpolata...