Version vom 17. Mai 2006, 15:00 Uhr

Inhaltsverzeichnis

1 Der BinarySearch

Der BinarySearch

Er wird verwendet um sortierte Arrays (z.B. mit BubbleSort vorsortiert) nach einer Zahl zu durchsuchen. Im Gegensatz zum einfachen Sort muß er nicht immer der gesammte Array durchgehen um die geeignete Position für die gegebene Zahl zu finden, weshalb sich die Verarbeitungsgeschwindigkeit eklatant verbessert wird. Durch diese Sortierweise können auch lange Arrays mit extrem geringem Zeit und Ressourcenaufwand geordnet werden.

Ich hab mir die Mühe gemacht, den Sort so zu schreiben, dass der Array nicht kopiert werden muß, sondern lediglich ein Speicherverweis dazu hergestellt wird. Das Array, welches als Quelle dient, wird einfach verändert, dies steigert die Effiziens.

Der Algorythmus

Der ganze Algorythmus ist als Methode verwirklicht worden. Dies ermöglicht die unveränderte übernahme des Quellcodes, siehe unten.

 Sub BinarySearch(ByRef a as int32, aL as int32, aSe as int32, ByRef aG as int32){
     var p1 as int32=0;
     var p2 as int32=aL;
     var b as boolean=true;
     var c as int32=0;
     
     While(b){
        aG=(p1+p2)/2;
        if(a[aG]<aSe){p1=aG;}
        if(a[aG]>aSe){p2=aG;}
        if((a[aG]+1)>aSe){
        if((a[aG]-1)<aSe){b=false;}}
           if(c>aL){b=false;aG=-1;}
        c++;
     }
  }

Der ultimative Test

Um den Suchalgorythmus zu testen, könnt ihr beispielsweise folgendes schreiben:

  var aLenght as int32 = 10;
  var arr[aLenght] as int32 = { 2, 9, 14, 16, 39, 48, 52, 70, 89, 94 };
  var aSearch as int32 = 29;
  var aGoal as int32 = 0;

  WriteLine(' ');
  WriteLine('Suche nach Zahl ' & aSearch & '...');
  WriteLine(' ');

  BinarySearch(arr,aLenght,aSearch,aGoal);
  
  if(aGoal<0){
     WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich nicht im angegebenen Array!');
  }
  else {
     WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich an Position ' & aGoal & '!');
  }
  
  aSearch = 39

  WriteLine(' ');
  WriteLine('Suche nach Zahl ' & aSearch & '...');
  WriteLine(' ');
  BinarySearch(arr,aLenght,aSearch,aGoal);
  
  if(aGoal<0){
     WriteLine('Die gesuchte Zahl befindet sich nicht im angegebenen Array!');
  }
  else {
     WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich an Position ' & aGoal & '!');
  }

Der Erfolg

  Script gestartet.
  
  Array vor der Sortierung:
  15 2 19 8 20 8 29 4
  
  Array nach der Sortierung:
  2 4 8 8 15 19 20 29
  
  Script beendet.

Viel Spaß mit BubbleSort!

MFG Proximo

Scripting:BinarySearch

Aus STNE-Wiki

Version vom 17. Mai 2006, 15:00 Uhr

Inhaltsverzeichnis

Der BinarySearch

Der Algorythmus

Der ultimative Test

Der Erfolg

Ansichten

Persönliche Werkzeuge

Navigation

Mitmachen

Starflyer - Wikizeitung

Script-Engine

Suche

Werkzeuge

@@ Zeile 10: / Zeile 10: @@
 Der ganze Algorythmus ist als Methode verwirklicht worden. Dies ermöglicht die unveränderte übernahme des Quellcodes, siehe unten.
-   Sub BubbleSort (ByRef a as integer, aLenght as integer){
+  Sub BinarySearch(ByRef a as int32, aL as int32, aSe as int32, ByRef aG as int32){
-       var i=0;
+       var p1 as int32=0;
-       var tmp;
+       var p2 as int32=aL;
-       While (++i<aLenght){
+      var b as boolean=true;
-          if (a[i-1]>a[i]){
+      var c as int32=0;
-            tmp=a[i-1];
-            a[i-1]=a[i];
+       While(b){
-            a[i]=tmp;
+         aG=(p1+p2)/2;
-            i=i-2;
+          if(a[aG]<aSe){p1=aG;}
-         }
+         if(a[aG]>aSe){p2=aG;}
-         if(i<0){i=0}
+         if((a[aG]+1)>aSe){
+         if((a[aG]-1)<aSe){b=false;}}
+            if(c>aL){b=false;aG=-1;}
+         c++;
        }
     }
@@ Zeile 26: / Zeile 29: @@
 ==Der ultimative Test==
-Um den Sort zu testen, könnt ihr beispielsweise folgendes schreiben:
+Um den Suchalgorythmus zu testen, könnt ihr beispielsweise folgendes schreiben:
+   var aLenght as int32 = 10;
+   var arr[aLenght] as int32 = { 2, 9, 14, 16, 39, 48, 52, 70, 89, 94 };
+   var aSearch as int32 = 29;
+   var aGoal as int32 = 0;
-   var aLaenge = 8;
-   var arr[aLaenge] as integer = { 15, 2, 19, 8, 20, 8, 29, 4 };
     WriteLine(' ');
-    WriteLine('Array vor der Sortierung:');
+    WriteLine('Suche nach Zahl ' & aSearch & '...');
-   WriteLine(arr[0] & ' ' & arr[1] & ' ' & arr[2] & ' ' & arr[3] & ' ' & arr[4] & ' ' & arr[5] & ' ' & arr[6] & ' ' & arr[7]);
-   BubbleSort(arr,aLaenge);
-   WriteLine(' ');
-   WriteLine('Array nach der Sortierung:');
-   WriteLine(arr[0] & ' ' & arr[1] & ' ' & arr[2] & ' ' & arr[3] & ' ' & arr[4] & ' ' & arr[5] & ' ' & arr[6] & ' ' & arr[7]);
     WriteLine(' ');
+   BinarySearch(arr,aLenght,aSearch,aGoal);
+   if(aGoal<0){
+      WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich nicht im angegebenen Array!');
+   }
+   else {
+      WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich an Position ' & aGoal & '!');
+   }
+   aSearch = 39
+   WriteLine(' ');
+   WriteLine('Suche nach Zahl ' & aSearch & '...');
+   WriteLine(' ');
+   BinarySearch(arr,aLenght,aSearch,aGoal);
+   if(aGoal<0){
+      WriteLine('Die gesuchte Zahl befindet sich nicht im angegebenen Array!');
+   }
+   else {
+      WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich an Position ' & aGoal & '!');
+   }
 ==Der Erfolg==