****************
*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