binäre Suche im 2 dim Feld

Slash86

Beginner

Posts: 2

Monday, April 20th 2009, 11:04pm

binäre Suche im 2 dim Feld

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

Delphi 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

SeBa

Master

Posts: 1,134

Friday, April 24th 2009, 2:52pm

Was mir aufgefallen ist, in der Matrix können Integer Werte drinstehen, aber deine Funktion kann, wenn ich das richtig gesehen hab, nur nach Byte suchen?

Slash86

Beginner

Posts: 2

Tuesday, April 28th 2009, 8:08pm

Verbesserte Version des binsearch Algorithmus

Habe außerdem Problem mit den Typen in der Parameterliste noch ein anderes Problem gefunden...desweiteren habe ich den Code selbst noch optimiert und mit Kommentaren versehen...Vielleicht ist es jetzt bequemer, mal ein Auge trüber zu werfen...

Delphi Quellcode

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:integer):ergebnis; 
 
var mitte_spalte: integer; 
links: integer; 
rechts: integer; 
zeile_o: integer; 
zeile_u: integer; 
zeilen_mitte: integer; 
gefunden: boolean; 
 
begin 
gefunden := false; 
 
//Variablenindizies fuer eine Zeile (nord/süd) 
zeile_o:=1; 
zeile_u:=n; 
zeilen_mitte:= (n+m) div 2; 
 
//Variablenindizies fuer eine Zeile (west/ost) in der Matrix 
rechts:= m; 
links := 1; 
 
//Schleife die im Worst Case gesamte Matrix absucht bis gefunden:=true oder unten = oben 
repeat 
//bineare Suche in den jeweiligen Zeilen der Matrix 
while (links <= rechts) and not gefunden do 
begin 
mitte_spalte:= (rechts + links) div 2; 
 
if Folge[zeilen_mitte,mitte_spalte] > key then 
rechts:=mitte_spalte-1 
else if Folge[zeilen_mitte,mitte_spalte] = key then 
gefunden:=true 
else links:=mitte_spalte+1; 
end; 
 
if not gefunden then 
begin 
 
if links = 1 then 
begin 
zeile_u:=zeilen_mitte-1; 
rechts:=m; 
end 
else if rechts = m then 
begin 
zeile_o:=zeilen_mitte+1; 
links:=1; 
end; 
 
end; 
 
until gefunden or (zeile_o >= zeile_u); 
 
if gefunden then 
begin 
result[1]:=zeilen_mitte; 
result[2]:=mitte_spalte; 
end 
else result[1]:=0; 
 
end;//Funktionsende 
 
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. 
 
//Ausgabe ist: 2 3