Einsendung:

Lösungsvorschlag für findIndex

Hi Volkard!
Ich habe folgenden Lösungsvorschlag anzubieten. Hierbei ist die Variable zaehl zu beachten, welche ich benutzt habe, um die Anzahl der Schleifendurchgänge zu zählen. Sie wurde global deklariert.

Das ist gut. Manchmal braucht man eben doch globale Variablen.

Es scheint eigentlich zu funktionieren, jedoch bin ich mir noch nicht sicher, ob dieses jetzt wirklich die schnellstmöglichste und beste Umsetzung des binären Suchens ist.

Es ist IMHO die schnellste.

Auf jeden Fall ist mir aufgefallen, daß Zahlen, die weiter oben im Index liegen, meist mehr (bei mein Testläufen war das nur einer) Durchläufe benötigen. Das liegt an den Stellen (zwei an der Zahl), an denen ich die mitte erzeuge. Denn wenn ich eine Mitte aus zwei Zahlen ermittle, dessen Differenz ungerade ist wie z.B. 10 und 5 dann nimmt die mitte immer den kleineren Wert an. Also in meinen Beispiel 7. Aber dafür gibt es wohl keine Lösung, oder?

Ich glaube, es gibt keine Lösung.
Die Suchzeiten in einem Array mit 10 Elementen sind:

0 2
1 2
2 2
3 2
4 2
5 2
6 3
7 4
8 4
9 4
summe 27

Die Verteilung ist sehr asymmetrisch. Das liegt wohl an

int oben=m_size-1, unten=0, mitte=int(m_size/2)-1;

Ich verstehe das

mitte=int(m_size/2)-1;

nicht. Mit

int oben=m_size-1, unten=0, mitte=int(m_size/2);

werden die Suchzeiten zu

0 3
1 3
2 3
3 2
4 2
5 2
6 2
7 3
8 3
9 3
summe 26

Für bessere Messergebnisse lasse ich auch die Summen für 1000000 Zahlen berechnen:

int oben=m_size-1, unten=0, mitte=int(m_size/2)-1;//19281703
int oben=m_size-1, unten=0, mitte=int(m_size/2);//19281706

Für andere Messergebnisse lasse ich auch die Summen für 5000000 Zahlen berechnen:

int oben=m_size-1, unten=0, mitte=int(m_size/2)-1;//108036175
int oben=m_size-1, unten=0, mitte=int(m_size/2);//108036172

Die beiden Zeilen sind also als gleich schnell zu erachten.

Da dies eine etwas anspruchsvolle Aufgabe war und ich schon einige Zeit damit verbracht habe, würde ich natürlich gerne Wissen ob es denn nun die richtige Lösung ist.

Sie ist genau richtig. Und die Aufgabe war so anspruchsvoll, daß es drei Monate gedauert hat, bis die erste Lösung (nämlich diese hier) eingegangen ist.
Bei der Durchsicht sind mir noch ein paar Kleinigkeiten aufgefallen, die den Kommentaren zu entnehmen sind:

int findIndex(const double &tofind)
{
   int exist=false;//nicht benötigt
   int oben=m_size-1, unten=0, mitte=int(m_size/2)-1;

   do
   {
      zaehl++;
      if (m_data[mitte]<=tofind)
      {
         unten=mitte;
         mitte=int(mitte+((oben-mitte)/2));
      }
      else
      {
         oben=mitte-1;
         mitte=(mitte-(mitte-unten)/2); 
      };
      if(oben-unten<=1)//Abfrage merken!
      {
         if(m_data[oben]==tofind)
            return oben;
         if(m_data[unten]==tofind)//else if
            return unten;
         else
            return -1;
      };
   }while(oben-unten!=1);//Die selbe Abfrage nochmal muß nicht sein
};

Das ergibt dann:

int findIndex(const double &tofind)
{
   int oben=m_size-1, unten=0, mitte=int(m_size/2);
   do
   {
      if (m_data[mitte]<=tofind)
      {
         unten=mitte;
         mitte=int(mitte+((oben-mitte)/2));
      }
      else
      {
         oben=mitte-1;
         mitte=int(mitte-(mitte-unten)/2); 
      };
   }while(oben-unten>1);
   
   if(m_data[oben]==tofind)
      return oben;
   else if(m_data[unten]==tofind)
      return unten;
   else
      return -1;
};


Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern.
[aktuelle Version] [inhalt] [index]      [Fehlerkorrektur, Verbesserungsvorschlag]

© Volkard Henkel <volkard@normannia.de>, last update: 08/25/00