Binäre Suche mit Zahlenblöcke

oliolioli · 09.02.10, 16:24

Hallo alle Miteinander!
Brauche dringend Hilfe

Ich hab vor 2 Wochen mit C++ programieren angefangen und soll nun von meim Praktikum aus ein Suchprogramm schreiben dass aus einer sortierten Liste von (Telefon-)Nummern (ca. ne millionen stk.) eine eingegebene Nummer sucht und dir sagt ob diese dabei ist oder nicht. Ich hab mich für die Binäresuche entschieden und bissher funktioniert das Programm auch ganz gut.
Dass problehm ist jetzt: Dass es Nummerblöcke gibt (10er; 100; oder auch 1000er Blöcke ) z.B. :
1
2
3
4
5
6
7
8
9
10
20
Also zwischen 10 und 20 wäre jetzt so ein Block.
Wie kann ich dem Programm sagen das es sich:
1.) um einen solchen Block handelt (denn es gibt NICHT alle Zahlen)
2.) dass alle Zahlen innerhalb von so einem Block vorhanden sind? (d.h. dass 10; 11;12;13;14;15;16;17;18;19;20 sehrwohl dabei sind)
Meine Idee bisher ist: Dass ich Zwischen Blöcke wie: 10 und 20 ein Zeichen einbau. Z.B. ein *.
8
9
10
*
20
Frage 1: Kann ich dem programm dann sagen, dass sich alle Zahlen vor und nach diesem bis zum vorherigen und zum nächsten (also von 10 bis 20) vorhanden sind?
Frage2 : Geht dass und oder Wie geht dass?
Frage 3 : Ist ein * überhaupt geeignet dafür?

Ein RIEßEN Dankeschön schonmal im vorraus!

Hir meine bisherige Binäresuche:

            
                    c++ Code: 
                  
                        #include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std;
 
void einfacherTest();
void TestMitEinlesen();
 
int main( int nargs, char **args )
{
  TestMitEinlesen();
 
  return 0;
} // main( int nargs, char **args )
 
double *binsuch( double feld[], size_t l, double zusuchen )
{
  if( l<1 )
  {
    // leeres Feld? Nichts gefunden!
    return NULL;
  }
  else if( l==1 )
  {
    // nur ein Element; vergleichen und ggf. zurückgeben:
    return ( feld[0]==zusuchen ? &feld[0] : NULL );
  }
  else
  {
    // Mehr als ein Element
    // Mitte suchen, und ggf. links oder rechts suchen:
    int index_Mitte = l/2;
    if( feld[index_Mitte]==zusuchen )
    {
      // Zufällig getroffen!
      return &feld[index_Mitte];
    }
    else if( feld[index_Mitte]>zusuchen )
    {
      // Mitte ist zu groß, also links weitersuchen
      return binsuch( feld, index_Mitte, zusuchen );
    }
    else
    {
      // Mitte zu klein, also in rechter Hälfte suchen:
      return binsuch( &feld[index_Mitte+1], l - index_Mitte - 1, zusuchen );
    }
  }
 
} // int *binsuch( int feld[], size_t l, int zusuchen )
 
void TestMitEinlesen()
{
  // Datei mit den sortierten Werten:
  string Dateiname;
  cout << "Bitte den Namen einer Datei mit sortierten int-Werten:" << endl;
  cin >> Dateiname;
 
  double *arr = NULL;
  size_t larr = 0;
 
  { // Einlesen
    ifstream f( Dateiname.c_str() );
    double wert;
    while( ( f>>wert ) )
    {
      // Feld um ein Element verlängern:
      arr = (double*)realloc( arr, ++larr*sizeof(double) );
      if( !arr )
      {
        cerr << "kein Speicher!\n";
        exit( 1 );
      }
      arr[larr-1] = wert;
    }
  } // Einlesen
 
  { // Testen, ob sortiert
    for( size_t i=1; i<larr; i++ )
    {
      if( !( arr[i-1]<arr[i] ) )
      {
        cerr << "Feld nicht sortiert!\n";
        exit( 1 );
      }
    }
  } // Testen, ob sortiert
 
  // Welcher Wert soll gesucht werden?
 
for(;1==1;){
  cout << "Gesuchten Wert eingeben:" << endl;
  double gesucht;
  cin >> gesucht;
 
  double *p_gefunden = binsuch( arr, larr, gesucht );
  if( p_gefunden )
  {
    cout << "In " << Dateiname << " gefunden: " << *p_gefunden << endl;
  }
  else
  {
    cout << "Wert in " << Dateiname << " nicht gefunden." << endl;
  }
  }
  // allokierten Speicher wieder freigeben:
  free( arr ); arr = NULL; larr = 0;
  
  system("pause");
 
} // void TestMitEinlesen()

**Maik** · 09.02.10, 16:27

Hi,

Zitat:

Zitat von oliolioli

Ich hab vor 2 Wochen mit C++ programieren angefangen und soll nun von meim Praktikum aus ein Suchprogramm schreiben

deinen Beitrag hast du im Forum für die Formatierungssprache CSS (Cascading Stylesheets) reingestellt

Ich leite deine Fragen dann mal an unser "C/C++"-Fachforum weiter.

mfg Maik

***deepthroat*** · 09.02.10, 20:41

Hi.

Also erstmal hättest du dir gar nicht soviel Arbeit machen müssen. Die STL bietet bereits einen binary_search Algorithmus bzw. den std::lower_bound Algorithmus an.

Außerdem gibt es auch einen adjacent_find Algorithmus, mit dem man prüfen kann, ob eine Sequenz sortiert ist:

            
                    cpp Code: 
                  
                        if (std::ajdacent_find(arr, arr + larr, std::greater_equal()) == (arr + larr)) {
  // sortiert bzw. keine Duplikate enthalten
}

Was ist das denn für ein Projekt? Eine Übungsaufgabe? Oder steckt da etwas Ernsthaftes dahinter?

Dann sollte man sich überleben ob es so günstig ist ein Array für die Speicherung zu benutzen. Ein Baum (z.B. Präfixbaum) würde sich da evtl. eher anbieten. Jetzt hast du ja nur double, die üblicherweise 8 Byte groß sind. sind also schon 8 MB.

Das Problem mit den Blöcken könntest du mit einer Klassenhierarchie lösen, wo eine Range definiert wird:

            
                    cpp Code: 
                  
                        class Entry {
public:
  virtual bool matches(double) const = 0;
  virtual bool operator<(double) const = 0;
};
 
class Range : public Entry {
  double m_lower, m_upper;
public:
  Range(double lower, double upper) : m_lower(lower), m_upper(upper) {}
 
  virtual bool matches(double v) const {
    return m_lower <= v && v <= m_upper;
  }
  virtual bool operator< (double v) const {
    return v < m_lower;
  }
};
 
int main( int nargs, char **args )
{
  Entry* v[] = { new Range(30., 35.) };
  size_t v_size = sizeof(v)/sizeof(*v);
  Entry** v_end = v + v_size;
 
  double value = 31.;
  
  Entry** p = std::lower_bound(v, v_end, value, std::mem_fun(&Entry::operator<));
 
  if (p == v_end) {
    cout << "no" << endl;
  } else if ((*p)->matches(value)) {
    cout << "yes" << endl;
  }
}

oliolioli · 10.02.10, 09:35

Vielen Dank für die hilfreiche antwort!! Ich versuch dass glaich mal umzusetzen.
Dass Programm is sowol Übungsaufgabe also auch ernst zugleich. Es soll später dazu dienen, Anrufe, die über einen unserer Serverlaufen, möglichst schnell einem Provider zuzuorden. (die tel. nummern sind in einer dazugehörigen Liste gespeichert.) Es soll nur sagen. Ja die nummer ist dabei/nicht dabei...
mfg oli