Hey,
habe mir gerade überlegt, wie man mit Pascal (in der Delphikonsole) ein Unterprogramm schreiben könnte, was eine binäre Suche in einem 2 dimensionalen Feld durchführt...vielleicht können die programmiererfahrernen Forumsteilnehmer mal ein Auge darauf werfen, um ihre Meinung kundzutun in Form von Verbesserungsvorschlägen,Kritiken etc.
Das 2D-Feld ist zeilweise und spaltenweise aufsteigend sortiert...in meinen Tests hats funktioniert, wenn das nur dumme Zufälle waren (und das jmd. auf Anhieb sieht), wäre es nett wenn ich auf die Fälle hingeweisen werden könnte...
Alles anzeigen
Gruß Slash
habe mir gerade überlegt, wie man mit Pascal (in der Delphikonsole) ein Unterprogramm schreiben könnte, was eine binäre Suche in einem 2 dimensionalen Feld durchführt...vielleicht können die programmiererfahrernen Forumsteilnehmer mal ein Auge darauf werfen, um ihre Meinung kundzutun in Form von Verbesserungsvorschlägen,Kritiken etc.
Das 2D-Feld ist zeilweise und spaltenweise aufsteigend sortiert...in meinen Tests hats funktioniert, wenn das nur dumme Zufälle waren (und das jmd. auf Anhieb sieht), wäre es nett wenn ich auf die Fälle hingeweisen werden könnte...
Quellcode
- program Suche_2D;
- {$APPTYPE CONSOLE}
- uses
- SysUtils;
- const n=3;
- m=3;
- type Matrix=array[1..n,1..m] of integer;
- ergebnis=array[1..2] of integer;
- function binsearch_dim2 (Folge: Matrix; n,m:integer;key:byte):ergebnis;
- var i,mitte_spalte,links,rechts,Zeile:integer;
- gefunden,Fehler:boolean;
- merke:array of boolean;
- begin
- Setlength(merke,n);
- gefunden := false;
- Fehler:=false;
- Zeile:= n div 2;
- rechts:= m;
- links := 1;
- for i:=1 to n do merke[i]:=false;
- while not gefunden and not Fehler do
- begin
- merke[Zeile]:=true;
- while (links <= rechts) and not gefunden do
- begin
- mitte_spalte:= (rechts + links) div 2;
- if Folge[zeile,mitte_spalte] > key then rechts:=mitte_spalte-1
- else if Folge[Zeile,mitte_spalte] = key then gefunden:=true
- else links:=mitte_spalte+1;
- end;
- if not gefunden and (links = 1) then
- begin
- Dec(Zeile);
- if (merke[Zeile] <> true) and (Zeile >= 1) then rechts:=m
- else Fehler:=true;
- end
- else if not gefunden and (rechts = m) then
- begin
- Inc(Zeile);
- if (merke[Zeile] <> true) and (Zeile <= n) then links:=1
- else Fehler:=true;
- end;
- end;
- merke:=nil;
- if not Fehler and gefunden then
- begin
- result[1]:=Zeile;
- result[2]:=mitte_spalte;
- end
- else result[1]:=0;
- end;
- var a:Matrix;
- begin
- //Test
- a[1,1]:=1;
- a[1,2]:=2;
- a[1,3]:=3;
- a[2,1]:=4;
- a[2,2]:=5;
- a[2,3]:=6;
- a[3,1]:=7;
- a[3,2]:=8;
- a[3,3]:=9;
- write(binsearch_dim2(a,n,m,8 )[1],' ',binsearch_dim2(a,n,m,8 )[2]);
- readln;
- end.
Gruß Slash