****************
            *BINÄRES SUCHEN*
            ****************

*
****************************
* WAS IST BINÄRES SUCHEN?? *
****************************

 NEHMEN WIR EINMAL AN, MAN WILL EIN
 VERWALTUNGSPROGRAMM FÜR DISKETTEN
 IN BASIC SCHREIBEN UND EINE SUCH-
 FUNKTION EINBAUEN, BEI DER MAN, Z.B.
 DEN NAMEN EINES DEMOS EINGIBT, UND
 DANN AUTOMATISCH DIE ID-NUMMER, USW.
 AUSGEGEBEN WIRD.

 WIE WIRD DER SUCH-ALGORITHMUS WAHR-
 SCHEINLICH AUSSEHEN?

 MEISTENS WOHL LINEAR, D.H., DAß ALLE
 DATENSÄTZE DER REIHE NACH DURCHSUCHT
 WERDEN. WENN WIR VON RUND 600 DATEN-
 SÄTZEN AUSGEHEN, UND MAN NIMMT AN, DAß
 DER GESUCHTE DATENSATZ NR.599 IST,
 KOMMT MAN IN BASIC AUF EINE NICHT
 UNERHEBLICHE RECHENZEIT.

 ES GIBT AUCH EINE SCHNELLERE UND
 EFFEKTIVERE MÖGLICHKEIT DEN GLEICHEN
 ERFOLG BEI 600 DATENSÄTZEN IN LEDIG-
 LICH 10 (ODER AUCH WENIGER) VERSUCHEN
 ZU ERZIELEN.

 DAS BINÄRE SUCHEN.

*
************************************
* WIE FUNKTIONIERT BINÄRES SUCHEN? *
************************************

 ZUERST: DAS BINÄRE SUCHEN KANN NUR DANN
 ANGEWANDT WERDEN, WENN DIE DATENSÄTZE
 IN SORTIERTER FORM VORLIEGEN! D.H., SIE
 MÜSSEN AUFSTEIGEND SORTIERT SEIN, ALSO
 Z.B. SO:

  1."ACCESS DENIED"       A<C
  2."COMA LIGHT 12"       C<R  C>A
  3."RADIO NAPALM 100%"   R<W  R>C
  4."WISHES"                   W>R

 ODER:

  1."78"                   78<163
  2."163"                 163<422
  3."422"                 422<...
  ...                       ...

 WENN WIR NUN 12 VARIABLEN MIT AUFSTEI-
 GENDEN WERTEN BIS 50 IN EINEM ARRAY
 HABEN, DIE DATENSTRUKTUR ALSO Z.B.
 FOLGENDERMAßEN AUSSIEHT:

   FELD      WERT
   ----      ----
     01        01   DIE DIFFERENZ
     02        05   ZWISCHEN DEN WERTEN
     03        07   IST BELIEBIG; AN DER
     04        20   12.TEN POSITION
     05        22   BETRÄGT DER WERT 50
     06        29
     07        32
     08        37
     09        41
   > 10 *    > 45 *
     11        47
     12        50

 WIR SUCHEN NUN DEN WERT "45", LINEAR
 WÜRDEN WIR ZEHN VERSUCHE BENÖTIGEN.
 BINÄR MAXIMAL VIER, WIE DAS?

 NUN, WIR TEILEN DEN SUCHBEREICH IMMER
 IN DIE HÄLFTE, DAS WÜRDE DANN SO AUS-
 SEHEN:

 1.   1+12=13  13/2=6 (ABGERUNDET!)
                 **
  01 02 03 04 05 06 07 08 09 10 11 12
 -------------------------------------
  01 05 07 20 22 29 32 37 41 45 47 50
                 **

 DANN UNTERSUCHEN WIR POSITION 6, SIE
 ENTHÄLT DEN WERT "29", DER GESUCHTE
 WERT "45" IST ABER GRÖßER, ALSO MUß
 ER SICH IN DER OBEREN HÄLFTE DES
 ARRAYS BEFINDEN, DA WIR DAS FELD AUF-
 STEIGEND SORTIERT HABEN!

 NUN HALBIEREN WIR WIEDERRUM DAS REST-
 LICHE FELD, IN DEM WIR DIE ZAHL VER-
 MUTEN, DABEI RUNDEN WIR AB, DENN EIN
 HALBES ARRAY GIBT ES NICHT:

 2.         6+12=18   18/2=9
                   **
       06  07  08  09  10  11  12
      ----------------------------
       29  32  37  41  45  47  50
                   **

 NUN ÜBERPRÜFEN WIR WIEDER DEN INHALT
 DES FELDES NR.9, ES ENTHÄLT DIE ZAHL
 "41", WIEDERUM KLEINER ALS DER GESUCHTE
 WERT (45), ALSO VERKLEINERN WIR DEN
 SUCHBEREICH WIEDER UM DIE HÄLFTE:

 3.   9+12=21   21/2=10
                 **
             09  10  11  12
            ----------------
             41  45  47  50
                 **

 NACH DEM AUSLESEN DES 10.TEN FELDES
 STELLEN WIR FEST, DAß WIR UNSERE ZAHL
 GEFUNDEN HABEN, UND DAS MIT NUR DREI
 VERSUCHEN!

 SOWEIT, SOGUT! ABER WAS TUN, WENN DER
 GESUCHTE WERT KLEINER ALS DER IN
 FELD 6 (=29), ALSO Z.B. 7 (FELD 3) IST?
 EINFACH DEN OBEREN RAND DES ARRAYS VON
 12 AUF 6 HERABSETZEN, DANN GEHT ES
 WIEDER WEITER MIT 1+6=7  7/2=3, USW...

 ALLGEMEIN LÄßT SICH ALSO SAGEN:

 INT (UNTERE GRENZE+OBERE GRENZE)/2
  =MITTE DES FELDES

 WOBEI DANACH GEPRÜFT WIRD, OB DER
 GESUCHTE WERT GRÖßER, KLEINER ODER
 GLEICH MIT DEM WERT IN DER MITTE DES
 FELDES IST.

 WENN DER WERT GRÖßER IST, WIRD DAS
 UNTERE ENDE DES ARRAYS (=UNTERGRENZE)
 AUF DIE MITTE DES FELDES ERHÖHT.

 WENN DER WERT KLEINER IST, WIRD DAS
 OBERE ENDE DES ARRAYS (=OBERGRENZE)
 AUF DIE MITTE DES FELDES GESETZT.

 NUN WIRD WIEDER DIE MITTE DES FELDES
 BERECHNET, UND NACH KLEINER, GRÖßER,
 BZW. GLEICH GEPRÜFT, WIE IM ERSTEN
 SCHRITT, UND IMMER SO WEITER, BIS DER
 WERT GEFUNDEN IST.


*
*************************************
* WIESO 3 VERSUCHE BEI 12 FELDERN?? *
*************************************

 TJA, DARUM HEIßT ES AUCH BINÄRES
 SUCHEN, DENN BEI JEDEM SCHRITT WIRD
 DAS ZU DURCHSUCHENDE FELD HALBIERT.
 WENN MAN DIES (VEREINFACHT) RÜCK-
 GÄNIG MACHEN WÜRDE, SÄHE ES FOLGEN-
 DERMAßEN AUS:

 2           =2   ODER   2 HOCH 1
 2*2         =4          2 HOCH 2
 2*2*2       =8          2 HOCH 3
 2*2*2*2     =16         2 HOCH 4
 2*2*2*2*2   =32         2 HOCH 5
 2*2*2*2*2*2 =64         2 HOCH 6

 ALSO DIE ZWEIER-POTENZEN. JEDER CODER
 DÜRFTE SIE KENNEN... WENN MAN DAS
 BINÄRE SUCHEN MATHEMATISCH BETRACHTET,
 DÜRFTE KLAR WERDEN, WARUM ES SO GENANNT
 WIRD:

 WENN WIR Z.B. DIE ZAHL 123 ALS MAXI-
 MALEN INDEX EINES ARRAYS NEHMEN.
 BINÄR WÜRDE SIE

           %01111011

 LAUTEN. NUN WIRD BEI DEM ERSTEN DURCH-
 LAUF DER SUCHROUTINE DAS FELD HALBIERT,
 BINÄR ALSO DIE BITS ALLE UM EINE STELLE
 NACH RECHTS VERSCHOBEN (LSR A IN ASS-
 EMBLER). DAS BYTE WÜRDE FOLGLICH SO
 AUSSEHEN:

           %00111101

 DIE VERSCHIEDENEN MÖGLICHKEITEN,
 WELCHEN INDEX DAS GESUCHTE FELD HABEN
 KANN WURDEN NUN AUF 61 EINGESCHRÄNKT.
 62 FELDER WURDEN FOLGLICH AUSGE-
 SCHLOSSEN. WENN MAN DIES NUN WEITER-
 FÜHRT, BLEIBT IM SCHLECHTESTEN FALL
 DIE MÖGLICHKEIT, DAß DER INDEX DURCH
 DAS LETZTE BIT GEKENNZEICHNET WIRD.

 ALLGEMEIN GILT, DAS MAN FÜR 2 HOCH N-
 ELEMENTE MAXIMAL N-VERSUCHE BENÖTIGT,
 WOBEI MAN FÜR N EINE BELIEBIGE ZAHL
 EINSETZEN KANN, HIER EIN BEISPIEL:

 IN EINEM FELD VON 1100 WIRD EINE ZAHL
 GESUCHT, NEHMEN WIR 599. MIT DEM
 BINÄREN SUCHEN SIND MAXIMAL 11 VERSUCHE
 NÖTIG, UM SIE ZU FINDEN... RECHNEN
 WIR MAL NACH:

    1100 = 2 HOCH 10 + 76
        -> ALSO WERDEN 11 BITS ZUR DAR-
           STELLUNG DIESER ZAHL BE-
           NÖTIGT -> MAXIMAL 11 VERSUCHE

 UG    OG    RECHENOPERATION       VERS.
 ---------------------------------------
 0001  1100  (0001+1100)/2=550 < 599   1
 0550  1100  (0550+1100)/2=825 > 599   2
 0550  0825  (0550+0825)/2=687 > 599   3
 0550  0687  (0550+0687)/2=618 > 599   4
 0550  0618  (0550+0618)/2=584 < 599   5
 0584  0618  (0584+0618)/2=601 > 599   6
 0584  0601  (0584+0601)/2=592 < 599   7
 0592  0601  (0592+0601)/2=596 < 599   8
 0596  0601  (0596+0601)/2=598 < 599   9
 0598  0601  (0598+0601)/2=599 = 599  10

                            TREFFER!!

 WIE BEREITS ZUVOR GESAGT, MAXIMAL 11
 VERSUCHE!

*
******************
* PROGRAMMIERUNG *
******************

 IN BASIC:

 05 MAX=10
 10 DIM FELD(MAX)
 12 FOR I=1 TO MAX
 14  READ A: FELD (I)=A
 16 NEXT          <- GENERIEREN DES
                             ARRAYS
 17 PRINT "GESUCHTE ZAHL?"
 18 INPUT ZAHL

 22 UGRENZE=1: OGRENZE=MAX

 30 X=INT((UGRENZE+OGRENZE)/2)
 32 PRINT UG,OG,X,FELD(X)
 34 IF UGRENZE>OGRENZE THEN GOTO 50
 36 IF ZAHL=FELD(X) THEN GOTO 60
 38 IF ZAHL>FELD(X) THEN UGRENZE=X+1
 40 IF ZAHL<FELD(X) THEN OGRENZE=X-1
 42 GOTO 30

 50 PRINT "ZAHL NICHT IM FELD VORHANDEN"
 52 END

 60 PRINT "INDEX DER GESUCHTEN ZAHL:"
 62 PRINT X
 64 END

 98 DATA 11, 34, 42, 67, 182, 506
 99 DATA 674, 867, 889, 910 <- DATEN
                           FÜR DAS ARRAY


 UND IN TURBO-PASCAL, FÜR DIE PC-FANS
 (SOLL'S JA AUCH GEBEN, HABE ICH GEHÖRT)

 PROGRAM BINSUCH;

 USES CRT;

 CONST   MAX=10;
         FELD:ARRAY(1..MAX) OF INTEGER
         =(11,34,42,67,182,506,674,
           867,889,910);

 VAR     ZAHL, OGRENZE, UGRENZE:INTEGER;
         ERGEBNIS:BOOLEAN;


 BEGIN
   CLRSCR;
   ERGEBNIS:=FALSE;
   WRITE ('GESUCHTE ZAHL? ');
   READLN (ZAHL);
   UGRENZE:=1; OGRENZE:=MAX;

   REPEAT
     X:=((UGRENZE+OGRENZE)DIV 2);
     IF ZAHL=FELD(X) THEN
       ERGEBNIS:=TRUE
     ELSE
       IF NUMMER>ZAHL(X) THEN
         UGRENZE=X+1
       ELSE
         OGRENZE=X-1;

   UNTIL (UGRENZE>OGRENZE) OR
         (ERGEBNIS=TRUE);

   IF ERGEBNIS=FALSE THEN
     WRITELN ('ZAHL NICHT GEFUNDEN!');
   ELSE
     WRITELN ('INDEX: ',X);

   READLN;
 END.

 DIE RUNDEN KLAMMERN, DIE DEN INDEX
 EINES ARRAYS KENNZEICHNEN SOLLTEN
 EIGENTLICH RECHTECKIG SEIN, ICH KONNTE
 DIE ZEICHEN IN DEM CHAR ALLERDINGS
 NICHT FINDEN...

                              RAM MAN...

S.U.C.K: WER ECKIGE KLAMMERN FÜR  SEINEN
TEXT BENÖTIGT,  SOLLTE/KANN  DIE  PFEIL-
TASTEN BENUTZEN. > < >, < >, < >
HERZLICHEN DANK AN  RAM MAN  FÜR  SEINEN
BEITRAG!  URSPRÜNGLICH  WOLLTE  ER  EINE
VERBESSERTE   VERSION   SEINES    TEXTES
ABGEBEN, ALLERDINGS HAT ER SICH BEI  MIR
FAST  EIN  VIERTEL   JAHR   NICHT   MEHR
GEMELDET,   UND  DIESE  VERSION   SEINES
TEXTES IST  EIGENTLICH  NICHT  UNBEDINGT
VERBESSERUNGSWÜRDIG.




Copyright 1997 X-Dome, Michael Steil