Interpolationssuche



  • Hi

    Ich habe folgendes Problem. Aufgabenstellung ist es eine Interpolationssuche in C zu implementieren. Das funktioniert auch super bis ein Wert gesucht werden soll, der nicht im Array vorkommt.

    Dann endet das ganze in einer Endlosshcleife, wie kann man das ganze umgehen ?

    void srch_int(long int x, long int aiValues[], long int n)
    {
    	int anf=0, end=n-1, m=0;           
    	count=0;                          
    
    	while(anf<=end && x!=aiValues[m])
    	{
    		m=anf+(end-anf)*(x-aiValues[anf])/(aiValues[end]-aiValues[anf]);                  // halbiere Intervall  
    		printf("\nm=%i, Val=%i",m,aiValues[m]);
    		getch();
    
    		if(x<aiValues[m])
    			end=m-1;              // suche im linken Intervall 
    
    		else
    			anf=m+1;                    // suche im rechten Intervall 
    
    		count++;
    	}
    
    	return;      
    }
    


  • wieso hast du da probleme?
    wenn du mit dem mitlaufenden index über das array hinaus bist, brichst du ab.
    du machst intervallteilung? wenn der intervall zu klein wird, abbrechen.



  • Naja die Sache ist die, wenn eine Zahl nicht vorhanden ist, dann ruft die Schleife immer und immer wieder dieselbe Arrayposition auf. DAs kann aber auch 2-3 mal passieren während eines normalen Suchdurchlaufes.

    Wie find ich also raus ob die Zahl im Array vorhanden ist oder nciht, denn wenn nciht soll ja abgebrochen werden.

    Vielen Dank



  • nimm einen neuen algorithmus.
    wozu rekursiv?
    machs doch iterativ. wenn du es so geschafft hast, kannste es ja auf rekursiv ummünzen, wenn es dann noch sein muss.



  • Das Ding ist doch iterativ, und leider so die Vorgabe der Aufgabenstellung. Und ganz ohne Witz ich komm leider echt absolut nicht weiter.



  • dann gib mal ein testprogramm mit einem gefüllten array, das den fehler produziert.
    dann noch, was rauskommen soll und wovon man ausgehen kann (array sortiert? was wird gesucht?)



  • Array füllen:

    int a[n];
    for(i=0;i<n;i++) 
        a[i]=rand();
    

    Funktionsaufruf:

    for(i=0;i<SEARCH;i++)
    {
        x=rand();
        srch_int(x,a,n);
    }
    

    Funktion:
    [cpp]
    void srch_int(long int x, long int a[], long int n)
    {
    int anf=0, end=n-1, m=0,mPrev=-1,iTemp;

    for(count=0;anf<=end && x!=a[m];count++)
    {
    iTemp=a[end]-a[anf];

    if(iTemp <= 0)
    break;

    m=anf+(end-anf)*(x-a[anf])/iTemp;

    if(mPrev==m)
    break;

    mPrev=m;

    if(x<a[m])
    end=m-1;

    else
    anf=m+1;
    }
    return;
    }



  • Shit, CPP Tag vergessen, hier nochmal richtig.
    Das Problem an der Sache ist, dass er in eine Endlosschleife kommt sobald m zwischen 3 Werten wechselt, also beispielsweise: m=6,m=7,m=8,m=6,m=7...

    Array füllen:

    int a[n];
    for(i=0;i<n;i++) 
        a[i]=rand();
    

    Funktionsaufruf:

    for(i=0;i<SEARCH;i++)
    {
        x=rand();
        srch_int(x,a,n);
        sum+=count;
    }
    

    Funktion:

    void srch_int(long int x, long int a[], long int n)
    {
    	int anf=0, end=n-1, m=0,mPrev=-1,iTemp;        
    
    	for(count=0;anf<=end && x!=a[m];count++)
    	{
            iTemp=a[end]-a[anf];
    
            if(iTemp <= 0)
                break;
    
            m=anf+(end-anf)*(x-a[anf])/iTemp;
    
            if(mPrev==m)
                break;
    
            mPrev=m;
    
    	  if(x<a[m])
    		end=m-1;              
    
    	  else
    	      anf=m+1;                   
    	}
    	return;      
    }
    


  • Erledigt, danke 🙂



  • kannst du mir mal erklären, was mit interpolationssuche gemeint sein soll?
    aus deinem algorithmus werd ich nicht wirklich schlau, vorallem weil der nichts zurückgibt.
    wenn ich z.b. als zahlen sowas hab...

    15   5   9   4  16   7  15   8  10  19   6   8   4   1   7
    

    hab was gefunden: http://de.wikipedia.org/wiki/Interpolationssuche


Log in to reply