www.mikrocontroller.net

Forum: PC-Programmierung Binäre Suche


Autor: jumper (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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!)

#include <iostream>
using namespace std;

int main ()
{


cout << "Bitte merken Sie sich eine Zahl zwischen [1,8]." << endl;
  char ans;
  cout << "Ist die Zahl kleiner als 5? (j|n): "; cin >> ans;
  if (ans == 'j')  
  {
    cout << "Ist die Zahl kleiner als 3? (j|n): ";  cin >> ans;
    if (ans == 'j') 
    {
      cout << "Ist die Zahl kleiner als 2? (j|n): ";  cin >> ans;
      if (ans == 'j') cout << "Ihre Zahl ist 1." << endl;
      else cout << "Ihre Zahl ist 2." << endl;
    }
    else  
    {
      cout << "Ist die Zahl kleiner als 4? (j|n): ";  cin >> ans;
      if (ans == 'j') cout << "Ihre Zahl ist 3." << endl;
      else cout << "Ihre Zahl ist 4." << endl;
    }
  }
  else  
  {
    cout << "Ist die Zahl kleiner als 7? (j|n): ";  cin >> ans;
    if (ans == 'j') 
    {
      cout << "Ist die Zahl kleiner als 6? (j|n): ";  cin >> ans;
      if (ans == 'j') cout << "Ihre Zahl ist 5." << endl;
      else cout << "Ihre Zahl ist 6." << endl;
    }
    else  
    {
      cout << "Ist die Zahl kleiner als 8? (j|n): ";  cin >> ans;
      if (ans == 'j') cout << "Ihre Zahl ist 7." << endl;
      else cout << "Ihre Zahl ist 8." << endl;
    }
  }
  return 0;
}


Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.
)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: spess53 (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Tim T. (tim_taylor)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Denke das sollte so am einfachsten sein:
#include <iostream>

using namespace std;

int main(void){
 unsigned int min=1;
 unsigned int max=8+1;
 char ans; 

 cout << "Bitte merken Sie sich eine Zahl zwischen [" << min << "," << max-1 << "]." << endl;

 while(min+1!=max){
  cout << "Ist die Zahl kleiner als " << (min+max)/2 << " ? (j|n): "; 
  cin >> ans;
  switch (ans){
   case 'j': max=(min+max)/2; break;
   case 'n': min=(min+max)/2; break;
   default : cout << "Fehler bei der Eingabe!" << endl;
  };
 };

 cout << "Ihre Zahl ist " << min << "." << endl;

 return 0;
}

Autor: jumper (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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
int main(void){
 unsigned int min=1;
 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.

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht 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"...

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Bitteschön, hier rekursiv:
// Time-stamp: "08.04.09 20:28 vonbis.cpp klaus -a-t- wachtler.de"

#include <iostream>


// fragt, ob die gesuchte Zahl kleiner ist als alsWas
bool istKleinerAls( int alsWas )
{
  std::cout << "Ist die Zahl kleiner als " << alsWas << "? j/n"
            << std::endl;
  char   antwort;
  while( ( std::cin >> antwort ), ( antwort!='j' && antwort!='n' ) )
  {
    // falsche Antworten, Leerzeichen, Zeilenvorschub etc. ueberlesen...
    // Ggf. hier falsche Eingaben abfangen, anstatt zu ignorieren
  }
  return antwort=='j';
}

// erraet eine Zahl, die zwischen kleinstwert und groesstwert liegt
// (jeweils einschliesslich)
int rateZahl( int kleinstwert, int groesstwert )
{
  int mittelwert = ( kleinstwert + groesstwert ) / 2;

  if( kleinstwert<groesstwert )
  {
    if( istKleinerAls( mittelwert+1 ) )
    {
      return rateZahl( kleinstwert, mittelwert );
    }
    else
    {
      return rateZahl( mittelwert + 1, groesstwert );
    }
  }
  else
  {
    return kleinstwert;
  }
}

int main( int nargs, char **args )
{
  const int   untereGrenze = 1, obereGrenze = 8;

  std::cout << "Bitte merken Sie sich eine Zahl zwischen "
            << untereGrenze << " und " << obereGrenze << "..."
            << std::endl;

  std::cout << "Zahl ist " << rateZahl( untereGrenze, obereGrenze ) << std::endl;
}

Autor: Εrnst B✶ (ernst)
Datum:

Bewertung
0 lesenswert
nicht 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"

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
woher soll ich wissen, wie DU sie erkennst? :-)

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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:
#include <iostream>
#include <algorithm>

static const int NUM_MIN = 1;
static const int NUM_MAX = 8;

using namespace std;

enum relation_t { R_TOO_SMALL, R_CORRECT, R_NOT_TOO_SMALL };

// Random-Access-Iterator für die Binärsuche
//
// Der Iterator ist äquivalent zu einer der Zahlen im Wertebereich. Die Zahl
// stellt quasi eine Adresse dar, die auf einen Wert des Typs relation_t zeigt,
// der wiederum angibt, ob die Zahl zu groß ist oder nicht. Dieser Wert steht
// aber nicht im Speicher, sondern wird bei der Dereferenzierung des Iterators
// mit * vom Benutzer abgefragt (s. operator*()).

class NumIt: public iterator<random_access_iterator_tag, relation_t> {
  public:
    // Initialisierung mit einem Zahlenwert
    NumIt(int num=0)          { m_num = num; }

    // Operatoren für Inkrement, Differenz und Derefernezierung
    NumIt &operator++()       { m_num++; return *this; }
    NumIt &operator+=(int d)  { m_num+=d; return *this; }
    int operator-(NumIt it)   { return m_num-it.m_num; }
    relation_t operator*();

    // Typecast-Operator für Ausgabe
    operator int()            { return m_num; };

  private:
    // Zahlenwert
    int m_num;
};

// Dereferenzierungsoperator, fragt den Wert vom Benutzer ab
relation_t NumIt::operator*() {
  char ans;
  while(true) {
    // Ist die Nummer des Iterators größer oder gleich der gesuchten Zahl?
    cout << "Ist die Zahl kleiner als " << m_num+1 << "? (j/n) ";
    cin >> ans;
    switch(ans) {
      case 'j':
        return R_NOT_TOO_SMALL;
      case 'n':
        return R_TOO_SMALL;
      default:
        cout << "Fehler in der Eingabe!" << endl;
    }
  }
}

int main() {
  NumIt it; // Ergebnisiterator

  cout << "Bitte merken Sie sich eine Zahl von " << NUM_MIN << " bis "
       << NUM_MAX << "." << endl;

  // Binärsuche aus der STL
  //
  // Gesucht wird in einer nur virtuell existierenden geordneten Liste das
  // Element mit dem Wert R_CORRECT. Da kein solches Element existiert (vom
  // Benutzer erfährt man nur, ob die Zahl zu klein ist oder nicht), liefert
  // lower_bound statt dessen das erste Element in der Liste, das nicht zu
  // klein ist. Weil die Liste geordnet ist, kann dies nur das richtige sein.

  it = lower_bound(NumIt(NUM_MIN), NumIt(NUM_MAX), R_CORRECT);

  // Ausgabe des Iteratornummer, also der gesuchten Zahl
  cout << "Ihre Zahl ist " << it << "." << endl;
  return 0;
}

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 :)

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schöne Idee!

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; zumindest erscheint das Ganze dann noch etwas 
abgedrehter.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht 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:
/* Time-stamp: "11.04.09 13:16 vonbis.c klaus@wachtler.de" */

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>

/* Dummyzeiger auf den Wert, der nur im Kopf des Benutzers existiert: */
const void *dummyKey_p = (void*)-1;

/* Die Vergleichsfunktion soll zwei Operanden vergleichen und bekommt
 * eigentlich Zeiger auf die Operanden übergeben (op1, op2).
 * Einer davon wird immer ein (dummy-)Zeiger auf den nicht
 * existierenden Schlüssel sein, der andere ein Zeiger in das nicht
 * existierende Feld ab NULL.
 * Letzterer wird als Wert interpretiert, der dem Anwender vorgelegt
 * wird zur Beurteilung, ob er zu klein/richtig/zu groß ist.
 */
int vergleichsfunktion( const void *op1, const void *op2 )
{
  printf( "op1=%d, op2=%d\n", (int)op1, (int)op2 );
  printf( "ist %d zu klein / richtig / zu gross?\n",
          (int)( op2==dummyKey_p ? op1 : op2 ) /* einer von beiden ist der
                                                * geratene Wert, der andere
                                                * ist der Suchschluessel! */
          );
  printf( "falls zu klein: k eingeben, "
          "falls gleich: = eingeben, "
          "falls zu gross: g eingeben!\n"
          );
  do
  {
    char Antwort = getchar();
    switch( Antwort )
    {
      case 'k':
        /* Angenommen, op1 ist der geratene Wert und op2 der
         * Schluessel, und der geratene Wert ist zu klein, dann muss
         * die Vergleichsfunktion einen Wert kleiner als 0 liefern
         * (egal welchen).
         * Ist op1 dagegen der Schlüssel, dann andersrum:
         */
        return ( op2==dummyKey_p ) ? -1 : +1;
        break;

      case '=':
        return 0;
        break;

      case 'g':
        /* Angenommen, op1 ist der geratene Wert und op2 der
         * Schluessel, und der geratene Wert ist zu gross, dann muss
         * die Vergleichsfunktion einen Wert groesser als 0 liefern
         * (egal welchen):
         */
        return ( op2==dummyKey_p ) ? +1 : -1;
        break;

      default :
        continue;
        break;
    }
  }
  while( "Merkel"!="ehrlich" ); /* Endlosschleife */
}

int main( int nargs, char **args )
{
  printf( "die gesuchte Zahl ist %d\n",
          (int)bsearch( dummyKey_p, /* Zeiger auf Suchschluessel */
                        (void*)1,   /* ab 1 testen */
                        8,          /* 8 "Feldelemente" testen */
                        1,          /* Groesse eines Elements */
                        vergleichsfunktion
                        )
          );


  return 0;
}

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!

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.