Frage zu Volkard Tutorial



  • Ich hab eine Frage zu dem Volkard Tutorial, da es ja ziemlich populär ist hoffe ich einfach das mir jemand weiterhelfen kann der das Tut schon mal gemacht hat. Oder vll. hilft mir ja Volkard persönlich.
    Ich bin grad beim binären-Suchen, und da war hier gegeben:http://www.volkard.de/vcppkold/binaeres_suchen__loesungsvorschlag_fuer_findindex.html folgender Lösungsvorschlag:

    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;
    };
    

    Ich verstehe den Lösungsvorschlag, aber in m_data[..] sind doch alle Sachen die drin stehen ungeordnet. Also z.B. ist m_data[1]=209 und m_data[80]=23 und m_data[33]=3.....aber die muss man beim binären Suchen doch Ordnen oder? Das kann doch eigentlich nur funktionieren wenn es eine Zahlenfolge gibt, also z.B. m_data[0]=3; m_data[1]=5; m_data[2]=10; m_data[3]=11; m_data[4]=15; m_data[5]25; m_data[6]=33;.......oder?
    Aber bei der Funktion von dem Lösungsvorschlag wird das doch gar nicht geordnet? Oder gehts auch ohne Ordnen? Das kann ich mir aber schlecht vorstellen. Wie will man den so ein ungeordnetes Array mit Binärer Suche durchsuchen? Oder hab ich grad irgendwie nen hänger?
    Also ich blicks net, meiner Meinung nach muss man des Ordnen!!!
    Kann mir bitte jemand helfen?
    Dankeschön schon mal im Voraus.



  • Eine solche Suche wendet man nicht auf Ungeordnetes an, da kannst du gleich linear Suchen. Sortieren lohnt nur dann wenn du oft suchen musst. Aber dann solltest du eventuell eine andere Datenstruktur verwenden.



  • die übung bestand aus zwei teilen:
    - Die findIndex-Methode muß neu programmiert werden, damit sie das neue Verfahren verwendet, und
    - die insert-Methode muß neu programmiert werden, damit sie die Sortierung aufrechterhält.

    in der lösung ist gemeinerweise die angepaßte insert-methode nicht zu finden.
    die könnte ungefäht so aussehen.

    void insert(const double &toInsert)
    {
       if(!has(toInsert))
       {
          m_data.grow(m_size+1);
          m_data[m_size]=toInsert;
          ++m_size;
    //ab hier neu
          //geh nach ganz hinten zum neuen
          int pos=m_size-1;
          //solange der aktelle kleiner ist als sein linker nachbar
          while(pos>=1 && m_data[pos]<m_data[pos-1])
          {
              //vertausche ihn mit dem linken nachbarn
              swap(m_data[pos],m_data[pos-1]);
              //und mach beim linken nachbarn weiter. 
              --pos;
          ]
       }
    }
    

Log in to reply