Forum: PC-Programmierung Binäre Suche


von jumper (Gast)


Lesenswert?

Muss ein Programm schreiben das eine zahl zwischen 1und 8 möglichst 
schnell ermittelt!

Habe das nun so gemacht!
Wie könnte ich es einfacher schreiben?
GIBT ES AUCH DIE MÖGLICHKEIT das ich nur mit j oder n antorten kann und 
bei allen anderen tasten die Meldung Erorr kommt!
(für diesen Fall wäre mir das mit dem if nicht klar!)
1
#include <iostream>
2
using namespace std;
3
4
int main ()
5
{
6
7
8
cout << "Bitte merken Sie sich eine Zahl zwischen [1,8]." << endl;
9
  char ans;
10
  cout << "Ist die Zahl kleiner als 5? (j|n): "; cin >> ans;
11
  if (ans == 'j')  
12
  {
13
    cout << "Ist die Zahl kleiner als 3? (j|n): ";  cin >> ans;
14
    if (ans == 'j') 
15
    {
16
      cout << "Ist die Zahl kleiner als 2? (j|n): ";  cin >> ans;
17
      if (ans == 'j') cout << "Ihre Zahl ist 1." << endl;
18
      else cout << "Ihre Zahl ist 2." << endl;
19
    }
20
    else  
21
    {
22
      cout << "Ist die Zahl kleiner als 4? (j|n): ";  cin >> ans;
23
      if (ans == 'j') cout << "Ihre Zahl ist 3." << endl;
24
      else cout << "Ihre Zahl ist 4." << endl;
25
    }
26
  }
27
  else  
28
  {
29
    cout << "Ist die Zahl kleiner als 7? (j|n): ";  cin >> ans;
30
    if (ans == 'j') 
31
    {
32
      cout << "Ist die Zahl kleiner als 6? (j|n): ";  cin >> ans;
33
      if (ans == 'j') cout << "Ihre Zahl ist 5." << endl;
34
      else cout << "Ihre Zahl ist 6." << endl;
35
    }
36
    else  
37
    {
38
      cout << "Ist die Zahl kleiner als 8? (j|n): ";  cin >> ans;
39
      if (ans == 'j') cout << "Ihre Zahl ist 7." << endl;
40
      else cout << "Ihre Zahl ist 8." << endl;
41
    }
42
  }
43
  return 0;
44
}

von Karl H. (kbuchegg)


Lesenswert?

jumper wrote:
> Muss ein Programm schreiben das eine zahl zwischen 1und 8 möglichst
> schnell ermittelt!
>
> Habe das nun so gemacht!

Von der grundsätzlichen Idee schon mal nicht schlecht.

> Wie könnte ich es einfacher schreiben?

Mit einer Schleife.


Du suchst Zahlen im zwischen 1 und 8. Diesen Grenzwerten geben wir mal 
einen Namen, nennen wir das eine Minimum und das andere Maximum (Gemeint 
ist jeweils der Bereich in dem die Zahl liegen könnte. 1 ist also das 
Minimum des Bereichs und 8 ist das Maximum.

Wann ist die Suche nach der Zahl abgeschlossen ( = 
Schleifenabbruchbedingung)?

Na offenbar dann, wenn du den Bereich so eingeschränkt hast, dass nur 
noch eine Zahl in Frage kommt. Wann ist das? Klar: Genau dann wenn 
Minimum gleich Maximum ist, dann kennst du die Zahl. In allen anderen 
Fällen gäbe es ja noch mehrere Wahlmöglichkeiten.

Mal angenommen, du weist die Zahl noch nicht. Also bietest du deinem 
Benutzer eine Zahl an und fragst ihn ob seine gedachte Zahl kleiner als 
diese Zahl ist. Welche bietest du ihm an?
Na, wenn Minimum gleich 1 ist, und Maximum gleich 8, dann bietest du ihm 
zb mal 4 an, weil 4 halbwegs in der Mitte zwischen 1 und 8 liegt. Wie 
könnte man das errechnen. zb so ( Minimum + Maximum ) / 2

Sagt der Benutzer ja, was bedeutet das dann für deinen Bereich. Mach dir 
das nochmal anhand konkreter Zahlen klar

 Das ist dein ursprünglicher Bereich

     Min                         Max
     1   2   3   4   5   6   7   8

Du fragst deinen Benutzer jetzt, was mit der 4 ist.
Er sagt, seine Zahl ist kleiner.
Wie schränkt das jetzt den Suchbereich ein.
Offenbar bleibt das Minimum gleich, aber das Maximum wechselt von 8 auf 
3 (weil 4 ja schon zu gross ist)  (//// kennzeichnet den Bereich in dem 
seine Zahl ganz sicher nicht mehr liegen kann)

     Min     Max
                 /////////////////
     1   2   3   4   5   6   7   8

Da Minimum nicht gleich Maximum ist, gehts in deiner Schleife in die 
nächste Runde und du fragst deinen Benutzer wieder ob ( 1 + 3 ) / 2 = 2 
kleiner als seine gedachte Zahl ist.

Der Benutzer teilt dir mit: Nein, ist es nicht

Was bedeutet das für deinen Suchbereich. 2 ist nicht kleiner, also kann 
1, das bisherige Minimum auch nicht kleiner sein. Du kennst also ein 
neues kleinstes Minimum, nämlich 2 und der Bereich der möglichen Werte 
schränkt sich ein zu

         Min Max
    ////         /////////////////
     1   2   3   4   5   6   7   8

(und jetzt wirds ein wenig trickreich, denn nach welcher Zahl fragst du 
jetzt. ( 2 + 3 ) / 2 = 2   Danach hast du aber schon mal gefragt. Auf 
der anderen Seite steht fest, dass der Benutzer sich entweder 2 oder 3 
gedacht hat, es also nur mehr 2 Möglichkeiten gibt. Am einfachsten ist 
es wohl, wenn deine Schleife in so einem Fall abbricht (wenn also der 
Suchbereich nur noch 2 mögliche Zahlen umfasst) und du den Benutzer 
direkt fragst: War es 2? Oder war es 3?

(Speziell das letzte Problem vereinfacht sich enorm, wenn du deinen 
Benutzer nicht einfach nur fragst, ob seine Zahl kleiner ist. Statt 
dessen fragst du ihn ob du seine Zahl erraten hast. Und erst wenn er 
dies verneint, fragst du ob deine Zahl kleiner als seine ist. In dem 
Fall kannst du dann nämlich die Zahl nach der du fragst in allen Fällen 
aus dem Suchbereich ausschliessen und der obige Sonderfall entsteht gar 
nicht mehr.

  Der Benutzer sagt 2 ist es nicht
  Nachfrage: kleiner/größer
  Benutzer sagt größer

und dein Suchbereich verändert sich zu

             Min
             Max
     //////      /////////////////
     1   2   3   4   5   6   7   8

und damit muss seine Zahl die 3 gewesen sein.
)

von Karl H. (kbuchegg)


Lesenswert?

jumper wrote:

> GIBT ES AUCH DIE MÖGLICHKEIT das ich nur mit j oder n antorten kann und
> bei allen anderen tasten die Meldung Erorr kommt!
> (für diesen Fall wäre mir das mit dem if nicht klar!)

Sicher geht das. Aber in deinem jetzigen Programm ist das sehr mühsam zu 
realisieren.

von spess53 (Gast)


Lesenswert?

Hi

1.Frage: Zahl>4?           nein: offset=0       ja: offset=4
2.Frage  Zahl>offset+2?    nein: offset=offset  ja: offset=offset+2
3.Frage  Zahl=offset+1?    nein: Zahl=offst+2   ja: Zahl=offset+1

Fertig.

MfG Spess

von Tim T. (tim_taylor) Benutzerseite


Lesenswert?

Denke das sollte so am einfachsten sein:
1
#include <iostream>
2
3
using namespace std;
4
5
int main(void){
6
 unsigned int min=1;
7
 unsigned int max=8+1;
8
 char ans; 
9
10
 cout << "Bitte merken Sie sich eine Zahl zwischen [" << min << "," << max-1 << "]." << endl;
11
12
 while(min+1!=max){
13
  cout << "Ist die Zahl kleiner als " << (min+max)/2 << " ? (j|n): "; 
14
  cin >> ans;
15
  switch (ans){
16
   case 'j': max=(min+max)/2; break;
17
   case 'n': min=(min+max)/2; break;
18
   default : cout << "Fehler bei der Eingabe!" << endl;
19
  };
20
 };
21
22
 cout << "Ihre Zahl ist " << min << "." << endl;
23
24
 return 0;
25
}

von jumper (Gast)


Lesenswert?

@Karl heinz Buchegger

Danke dir! echt gut erklärt! Werde ich später gleich mal programmieren!

@ Das sieht ja mal sehr gut aus und funktioniert ja auch ! :-)
Nur mir ist noch nicht ganz klar weshalb
die Schleife durchlaufen muß solange (min+1!=max) hätte gedacht das sie 
durchlaufen muß solange (min!=max) ist!
Naja muß ich nochmals kurz durchüberlegen!
Danke euch nochmals!

von Karl H. (kbuchegg)


Lesenswert?

jumper wrote:

> die Schleife durchlaufen muß solange (min+1!=max) hätte gedacht das sie
> durchlaufen muß solange (min!=max) ist!

Schau dir nochmal den Anfang des Programms an
1
int main(void){
2
 unsigned int min=1;
3
 unsigned int max=8+1;

Hmm. Wie war noch mal dein Bereich?  1 bis 8?

Viele Wege führen nach Rom.
Das Prinzip der Einschränkung des Suchbereichs, indem man eine Hälfte 
ausschliessen kann, ist immer gleich. Das ist das Prinzip des binären 
Suchens. Aber implementieren kann man das auf viele Arten.

von Εrnst B. (ernst)


Lesenswert?

Hmm... garkeine rekursive Lösung dabei...

Wär vielleicht fürs Verständnis nicht schlecht, das Programm auch mal 
mit rekursiven Funktionsaufrufen zu formulieren.
also in der Form:
main ruft auf "rate_zahl(1,8)", das ruft auf rate_zahl(1-4), dann 
rate_zahl(2-3), dann Ausgabe, "Zahl war 2"...

von Klaus W. (mfgkw)


Lesenswert?

Bitteschön, hier rekursiv:
1
// Time-stamp: "08.04.09 20:28 vonbis.cpp klaus -a-t- wachtler.de"
2
3
#include <iostream>
4
5
6
// fragt, ob die gesuchte Zahl kleiner ist als alsWas
7
bool istKleinerAls( int alsWas )
8
{
9
  std::cout << "Ist die Zahl kleiner als " << alsWas << "? j/n"
10
            << std::endl;
11
  char   antwort;
12
  while( ( std::cin >> antwort ), ( antwort!='j' && antwort!='n' ) )
13
  {
14
    // falsche Antworten, Leerzeichen, Zeilenvorschub etc. ueberlesen...
15
    // Ggf. hier falsche Eingaben abfangen, anstatt zu ignorieren
16
  }
17
  return antwort=='j';
18
}
19
20
// erraet eine Zahl, die zwischen kleinstwert und groesstwert liegt
21
// (jeweils einschliesslich)
22
int rateZahl( int kleinstwert, int groesstwert )
23
{
24
  int mittelwert = ( kleinstwert + groesstwert ) / 2;
25
26
  if( kleinstwert<groesstwert )
27
  {
28
    if( istKleinerAls( mittelwert+1 ) )
29
    {
30
      return rateZahl( kleinstwert, mittelwert );
31
    }
32
    else
33
    {
34
      return rateZahl( mittelwert + 1, groesstwert );
35
    }
36
  }
37
  else
38
  {
39
    return kleinstwert;
40
  }
41
}
42
43
int main( int nargs, char **args )
44
{
45
  const int   untereGrenze = 1, obereGrenze = 8;
46
47
  std::cout << "Bitte merken Sie sich eine Zahl zwischen "
48
            << untereGrenze << " und " << obereGrenze << "..."
49
            << std::endl;
50
51
  std::cout << "Zahl ist " << rateZahl( untereGrenze, obereGrenze ) << std::endl;
52
}

von Εrnst B. (ernst)


Lesenswert?

Uiiih, sehr schön.
Geradezu ein Lehrbuch-Beispiel.
Auf zu Lektion Zwei:

Wie erkenne ich eine Endrekursion/Tail recursion, wie löse ich diese 
auf, und warum kommt dann die Lösung von Tim dabei raus?

Aber die kommt vermutlich erst nächste Woche dran, wenn die Hausaufgabe 
lautet:
"Erweitere dein Programm, so dass es mit beliebigen Zahlenbereichen 
arbeitet, und nicht nur von 1 bis 8"

von Klaus W. (mfgkw)


Lesenswert?

woher soll ich wissen, wie DU sie erkennst? :-)

von yalu (Gast)


Lesenswert?

Nachdem gezeigt wurde, wie man die Aufgabe iterativ, und wie man sie
rekursiv löst, kommt nun eine Variante, die auf die explizite Iteration
und Rekursion komplett verzichtet, das Rad nicht neu erfindet und statt
dessen die eigentliche Binärsuche durch eine Funktion aus der Standard-
bibliothek erledigen lässt.

Die Funktion lower_bound, die dafür verwendet wird, erwartet die zu
durchsuchenden Elemente in einer Sequenz, die durch einen Iterator auf
das erste und letzte Element definiert ist. Üblicherweise handelt es
sich bei dieser Sequenz um einen im Speicher liegenden Container (Vektor
oder Liste).

Normalerweise sind die STL-Klassen und -Funktionen sehr einfach in der
Handhabung. Die vorliegende Anwendung stellt aber einen etwas kniffli-
geren Sonderfall dar, weil hier die Sequenz nicht im Hauptspeicher des
Computers, sondern im Gehirn des Benutzers liegt. Da aber alle Zugriffe
auf die Sequenzelemente über Iteratoren erfolgen, kann das Problem
gelöst werden, indem der Zugriffsoperator auf die Elemente so definiert
wird, dass er den Inhalt des "externen Speichers" per Benutzeranfrage
"ausgelesen" wird.

Das Ganze ist für den, der erst ein paar Tage C++ programmiert, sicher
maximal undurchsichtig. Es zeigt aber schön, welche weitreichenden
Abstraktionsmöglichkeiten diese Sprache und die zugehörige Standard-
bibliothek bieten.

Obwohl das Programm den fertigen Algorithmus aus der STL benutzt, ist es
wegen der notwendigen Iteratorklasse deutlich länger als die von Tim T.
gepostete ausprogrammierte Variante, so dass diese im konkreten Fall
natürlich zu bevorzugen ist. Wenn aber die Binärsuche ein wirklich
komplizierter Algorithmus mit ein paar tausend Codezeilen wäre, würde
man sich schon genau überlegen, ob man diesen mit viel Aufwand
neuprogrammiert oder lieber ein paar Verrenkungen wie die gezeigten in
Kauf nimmt, um ihn zur Anwendung passend zu machen.

Und hier ist der C++-Code:
1
#include <iostream>
2
#include <algorithm>
3
4
static const int NUM_MIN = 1;
5
static const int NUM_MAX = 8;
6
7
using namespace std;
8
9
enum relation_t { R_TOO_SMALL, R_CORRECT, R_NOT_TOO_SMALL };
10
11
// Random-Access-Iterator für die Binärsuche
12
//
13
// Der Iterator ist äquivalent zu einer der Zahlen im Wertebereich. Die Zahl
14
// stellt quasi eine Adresse dar, die auf einen Wert des Typs relation_t zeigt,
15
// der wiederum angibt, ob die Zahl zu groß ist oder nicht. Dieser Wert steht
16
// aber nicht im Speicher, sondern wird bei der Dereferenzierung des Iterators
17
// mit * vom Benutzer abgefragt (s. operator*()).
18
19
class NumIt: public iterator<random_access_iterator_tag, relation_t> {
20
  public:
21
    // Initialisierung mit einem Zahlenwert
22
    NumIt(int num=0)          { m_num = num; }
23
24
    // Operatoren für Inkrement, Differenz und Derefernezierung
25
    NumIt &operator++()       { m_num++; return *this; }
26
    NumIt &operator+=(int d)  { m_num+=d; return *this; }
27
    int operator-(NumIt it)   { return m_num-it.m_num; }
28
    relation_t operator*();
29
30
    // Typecast-Operator für Ausgabe
31
    operator int()            { return m_num; };
32
33
  private:
34
    // Zahlenwert
35
    int m_num;
36
};
37
38
// Dereferenzierungsoperator, fragt den Wert vom Benutzer ab
39
relation_t NumIt::operator*() {
40
  char ans;
41
  while(true) {
42
    // Ist die Nummer des Iterators größer oder gleich der gesuchten Zahl?
43
    cout << "Ist die Zahl kleiner als " << m_num+1 << "? (j/n) ";
44
    cin >> ans;
45
    switch(ans) {
46
      case 'j':
47
        return R_NOT_TOO_SMALL;
48
      case 'n':
49
        return R_TOO_SMALL;
50
      default:
51
        cout << "Fehler in der Eingabe!" << endl;
52
    }
53
  }
54
}
55
56
int main() {
57
  NumIt it; // Ergebnisiterator
58
59
  cout << "Bitte merken Sie sich eine Zahl von " << NUM_MIN << " bis "
60
       << NUM_MAX << "." << endl;
61
62
  // Binärsuche aus der STL
63
  //
64
  // Gesucht wird in einer nur virtuell existierenden geordneten Liste das
65
  // Element mit dem Wert R_CORRECT. Da kein solches Element existiert (vom
66
  // Benutzer erfährt man nur, ob die Zahl zu klein ist oder nicht), liefert
67
  // lower_bound statt dessen das erste Element in der Liste, das nicht zu
68
  // klein ist. Weil die Liste geordnet ist, kann dies nur das richtige sein.
69
70
  it = lower_bound(NumIt(NUM_MIN), NumIt(NUM_MAX), R_CORRECT);
71
72
  // Ausgabe des Iteratornummer, also der gesuchten Zahl
73
  cout << "Ihre Zahl ist " << it << "." << endl;
74
  return 0;
75
}

Disclaimer: Ich bin selber kein C++-Guru, deswegen kann ich nicht
garantieren, dass die Binärsuche aus der STL nicht auch auf einfachere
Weise für den vorliegenden Zweck genutzt werden kann. Für Verbesserungs-
vorschläge bin ich deswegen weit offen :)

von Klaus W. (mfgkw)


Lesenswert?

Schöne Idee!

Noch etwas C++-mäßiger wäre es vielleicht, zur Ausgabe nicht nach int zu 
wandeln, sondern direkt
1
   std::ostream &operator<<(std::ostream&,const NumIt&)
zu definieren; zumindest erscheint das Ganze dann noch etwas 
abgedrehter.

von Klaus W. (mfgkw)


Lesenswert?

ach ja: eine kleine Abkürzung wäre, R_CORRECT und R_NOT_TOO_SMALL 
zusmmenzufassen zu einem Wert (also z.B. R_CORRECT weg zu lassen und 
stattdessen R_NOT_TOO_SMALL zu nehmen).

(Bei der Gelegenheit könnte die enum auch gleich in die Klasse, z.B. als 
public.)

Aber immer noch eine schicke Idee!

von yalu (Gast)


Lesenswert?

Klaus Wachtler:

Vielen Dank für die Hinweise.

> Noch etwas C++-mäßiger wäre es vielleicht, zur Ausgabe nicht nach int zu
> wandeln, sondern direkt
>
>    std::ostream &operator<<(std::ostream&,const NumIt&)
>
> zu definieren;

Das hatte ich zuerst auch so. Dann habe ich mir überlegt, dass man
vielleicht irgendwann einmal das Ergebnis der Suche nicht nur ausgeben,
sondern als Integerzahl in weiteren Berechnungen verwenden möchte. Mit
dem Typecast-Operator sind gleich beide Fälle erschlagen, und man
braucht keine Friend-Deklaration für den Zugriff auf das private Element
m_num. Ist aber sicher auch etwas Geschmackssache.

> ach ja: eine kleine Abkürzung wäre, R_CORRECT und R_NOT_TOO_SMALL
> zusmmenzufassen zu einem Wert (also z.B. R_CORRECT weg zu lassen und
> stattdessen R_NOT_TOO_SMALL zu nehmen).

Stimmt, der R_CORRECT-Wert ist völlig überflüssig und trägt wahrschein-
lich mehr zur Verwirrung als zum Verständnis bei.

> (Bei der Gelegenheit könnte die enum auch gleich in die Klasse, z.B.
> als public.)

Ich weiß nur nicht richtig, wie ich dann das Enum als Template-Argument
an die Basisklasse iterator<random_access_iterator_tag, relation_t> von
NumIt übergeben kann. Mit irgendwelchen Vorwärtsdeklarationen habe ich
es nicht hinbekommen. Gibt es da einen Trick?

von Karl H. (kbuchegg)


Lesenswert?

Hmm. Du bringst mich auf eine Idee.
Mal sehen, wenn ich Zeit habe probier ich das mal aus.

Man kann ja lower_bound auch eine eigene Vergleichsfunktion unterjubeln. 
Die Idee ist dann: befülle einen Vector mit den Bereichswerten, und lass 
lower_bound nach irgendeinem Wert suchen (welcher ist ziemlich egal). 
Die Vergleichsfunktion (Vergleichsobjekt) gibst du lower_bound mit und 
darin machst du die Benutzerabfrage.

von yalu (Gast)


Lesenswert?

> Die Idee ist dann: befülle einen Vector mit den Bereichswerten, und
> lass lower_bound nach irgendeinem Wert suchen (welcher ist ziemlich
> egal).

Ja, das sollte so gehen. Man erspart sich damit die Deklaration einer
neuen Iteratorklasse und muss nur eine einzelne Funktion definieren.
Dafür hat man halt einen ansonsten nutzlosen Vektor im Speicher
herumliegen, was aber bei 8 Elementen noch kein Problem darstellt.

von Klaus W. (mfgkw)


Lesenswert?

@yalu:

Dein mieser Trick mit dem gedachten Feld und dem Suchschlüssel
im Kopf statt im Speicher geht übrigens auch in C!

Dort gibt es ja bsearch(), die aber nicht nur auf "kleiner"
testet, sondern "kleiner" oder "gleich" oder "groesser" wissen will.

Damit wird es in C auch noch kürzer:
1
/* Time-stamp: "11.04.09 13:16 vonbis.c klaus@wachtler.de" */
2
3
#include <stdlib.h>
4
#include <stddef.h>
5
#include <stdio.h>
6
7
/* Dummyzeiger auf den Wert, der nur im Kopf des Benutzers existiert: */
8
const void *dummyKey_p = (void*)-1;
9
10
/* Die Vergleichsfunktion soll zwei Operanden vergleichen und bekommt
11
 * eigentlich Zeiger auf die Operanden übergeben (op1, op2).
12
 * Einer davon wird immer ein (dummy-)Zeiger auf den nicht
13
 * existierenden Schlüssel sein, der andere ein Zeiger in das nicht
14
 * existierende Feld ab NULL.
15
 * Letzterer wird als Wert interpretiert, der dem Anwender vorgelegt
16
 * wird zur Beurteilung, ob er zu klein/richtig/zu groß ist.
17
 */
18
int vergleichsfunktion( const void *op1, const void *op2 )
19
{
20
  printf( "op1=%d, op2=%d\n", (int)op1, (int)op2 );
21
  printf( "ist %d zu klein / richtig / zu gross?\n",
22
          (int)( op2==dummyKey_p ? op1 : op2 ) /* einer von beiden ist der
23
                                                * geratene Wert, der andere
24
                                                * ist der Suchschluessel! */
25
          );
26
  printf( "falls zu klein: k eingeben, "
27
          "falls gleich: = eingeben, "
28
          "falls zu gross: g eingeben!\n"
29
          );
30
  do
31
  {
32
    char Antwort = getchar();
33
    switch( Antwort )
34
    {
35
      case 'k':
36
        /* Angenommen, op1 ist der geratene Wert und op2 der
37
         * Schluessel, und der geratene Wert ist zu klein, dann muss
38
         * die Vergleichsfunktion einen Wert kleiner als 0 liefern
39
         * (egal welchen).
40
         * Ist op1 dagegen der Schlüssel, dann andersrum:
41
         */
42
        return ( op2==dummyKey_p ) ? -1 : +1;
43
        break;
44
45
      case '=':
46
        return 0;
47
        break;
48
49
      case 'g':
50
        /* Angenommen, op1 ist der geratene Wert und op2 der
51
         * Schluessel, und der geratene Wert ist zu gross, dann muss
52
         * die Vergleichsfunktion einen Wert groesser als 0 liefern
53
         * (egal welchen):
54
         */
55
        return ( op2==dummyKey_p ) ? +1 : -1;
56
        break;
57
58
      default :
59
        continue;
60
        break;
61
    }
62
  }
63
  while( "Merkel"!="ehrlich" ); /* Endlosschleife */
64
}
65
66
int main( int nargs, char **args )
67
{
68
  printf( "die gesuchte Zahl ist %d\n",
69
          (int)bsearch( dummyKey_p, /* Zeiger auf Suchschluessel */
70
                        (void*)1,   /* ab 1 testen */
71
                        8,          /* 8 "Feldelemente" testen */
72
                        1,          /* Groesse eines Elements */
73
                        vergleichsfunktion
74
                        )
75
          );
76
77
78
  return 0;
79
}

Ich denke mir alle Zahlen ab der Adresse NULL, und jedes Byte ab
dort steht für den Zahlenwert seiner Adresse (also verwende ich die 
Adressen 1 bis 8, ohne darauf zuzugreifen).

Schönheitsfehler: bei bsearch() könnte es auch vorkommen, dass ein
gesuchtes Element nicht im Feld ist.
Deshalb wird auch nochmal nach dem richtigen Wert gefragt, wenn er
schon der letzte und einzige im restlichen Teilfeld ist.
Mit dem Wissen, dass das "Feld" vollständig ist, könnte man sich
diesen letzten Test sparen; bsearch() hat dieses Wissen aber nicht.
Um das zu beheben, muesste man bsearch() für die kleiner-Bedingung
umfrisieren (was nicht schwer ist, aber dann halt nicht mehr mit
der Std-Lib arbeitet).

Ansonsten: frohes Suchen und dicke Eier!

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.