binäre Suche im 2 dim Feld

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

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

    Quellcode

    1. program Suche_2D;
    3. {$APPTYPE CONSOLE}
    5. uses
    6. SysUtils;
    8. const n=3;
    9. m=3;
    11. type Matrix=array[1..n,1..m] of integer;
    12. ergebnis=array[1..2] of integer;
    14. function binsearch_dim2 (Folge: Matrix; n,m:integer;key:byte):ergebnis;
    16. var i,mitte_spalte,links,rechts,Zeile:integer;
    17. gefunden,Fehler:boolean;
    18. merke:array of boolean;
    20. begin
    21. Setlength(merke,n);
    22. gefunden := false;
    23. Fehler:=false;
    24. Zeile:= n div 2;
    25. rechts:= m;
    26. links := 1;
    28. for i:=1 to n do merke[i]:=false;
    31. while not gefunden and not Fehler do
    32. begin
    33. merke[Zeile]:=true;
    35. while (links <= rechts) and not gefunden do
    36. begin
    38. mitte_spalte:= (rechts + links) div 2;
    40. if Folge[zeile,mitte_spalte] > key then rechts:=mitte_spalte-1
    41. else if Folge[Zeile,mitte_spalte] = key then gefunden:=true
    42. else links:=mitte_spalte+1;
    43. end;
    45. if not gefunden and (links = 1) then
    46. begin
    47. Dec(Zeile);
    49. if (merke[Zeile] <> true) and (Zeile >= 1) then rechts:=m
    50. else Fehler:=true;
    52. end
    53. else if not gefunden and (rechts = m) then
    54. begin
    55. Inc(Zeile);
    57. if (merke[Zeile] <> true) and (Zeile <= n) then links:=1
    58. else Fehler:=true;
    60. end;
    61. end;
    62. merke:=nil;
    64. if not Fehler and gefunden then
    65. begin
    66. result[1]:=Zeile;
    67. result[2]:=mitte_spalte;
    68. end
    69. else result[1]:=0;
    70. end;
    72. var a:Matrix;
    74. begin
    75. //Test
    76. a[1,1]:=1;
    77. a[1,2]:=2;
    78. a[1,3]:=3;
    79. a[2,1]:=4;
    80. a[2,2]:=5;
    81. a[2,3]:=6;
    82. a[3,1]:=7;
    83. a[3,2]:=8;
    84. a[3,3]:=9;
    85. write(binsearch_dim2(a,n,m,8 )[1],' ',binsearch_dim2(a,n,m,8 )[2]);
    86. readln;
    87. end.
    Alles anzeigen


    Gruß Slash

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

    Quellcode

    1. const n=3;
    2. m=3;
    4. type Matrix=array[1..n,1..m] of integer;
    5. ergebnis=array[1..2] of integer;
    8. function binsearch_dim2 (Folge: Matrix; n,m:integer;key:integer):ergebnis;
    10. var mitte_spalte: integer;
    11. links: integer;
    12. rechts: integer;
    13. zeile_o: integer;
    14. zeile_u: integer;
    15. zeilen_mitte: integer;
    16. gefunden: boolean;
    18. begin
    19. gefunden := false;
    21. //Variablenindizies fuer eine Zeile (nord/süd)
    22. zeile_o:=1;
    23. zeile_u:=n;
    24. zeilen_mitte:= (n+m) div 2;
    26. //Variablenindizies fuer eine Zeile (west/ost) in der Matrix
    27. rechts:= m;
    28. links := 1;
    30. //Schleife die im Worst Case gesamte Matrix absucht bis gefunden:=true oder unten = oben
    31. repeat
    32. //bineare Suche in den jeweiligen Zeilen der Matrix
    33. while (links <= rechts) and not gefunden do
    34. begin
    35. mitte_spalte:= (rechts + links) div 2;
    37. if Folge[zeilen_mitte,mitte_spalte] > key then
    38. rechts:=mitte_spalte-1
    39. else if Folge[zeilen_mitte,mitte_spalte] = key then
    40. gefunden:=true
    41. else links:=mitte_spalte+1;
    42. end;
    44. if not gefunden then
    45. begin
    47. if links = 1 then
    48. begin
    49. zeile_u:=zeilen_mitte-1;
    50. rechts:=m;
    51. end
    52. else if rechts = m then
    53. begin
    54. zeile_o:=zeilen_mitte+1;
    55. links:=1;
    56. end;
    58. end;
    60. until gefunden or (zeile_o >= zeile_u);
    62. if gefunden then
    63. begin
    64. result[1]:=zeilen_mitte;
    65. result[2]:=mitte_spalte;
    66. end
    67. else result[1]:=0;
    69. end;//Funktionsende
    71. var a:Matrix;
    73. begin
    74. //Test
    75. a[1,1]:=1;
    76. a[1,2]:=2;
    77. a[1,3]:=3;
    78. a[2,1]:=4;
    79. a[2,2]:=5;
    80. a[2,3]:=6;
    81. a[3,1]:=7;
    82. a[3,2]:=8;
    83. a[3,3]:=9;
    84. write(binsearch_dim2(a,n,m, 8 )[1],' ',binsearch_dim2(a,n,m, 8 [2]);
    85. readln;
    86. end.
    88. //Ausgabe ist: 2 3
    Alles anzeigen


    ----------------------------------------------------------------
    Edit:
    Bitte das Syntax Highlighting unter dem Editor beachten.