Scripting:BinarySearch

Aus STNE-Wiki

(Unterschied zwischen Versionen)
Wechseln zu: Navigation, Suche
K
 
(Der Versionsvergleich bezieht 23 dazwischenliegende Versionen mit ein.)
Zeile 1: Zeile 1:
 +
{{Scriptingmenue}}
 +
=Der BinarySearch=
=Der BinarySearch=
Er wird verwendet um sortierte Arrays (z.B. mit [[Scripting:BubbleSort|BubbleSort]] vorsortiert) nach einer Zahl zu durchsuchen.
Er wird verwendet um sortierte Arrays (z.B. mit [[Scripting:BubbleSort|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.
+
BinarySearch ist erheblich schneller wie ein Linearer Search, spart Ressourcen sowie Rechen- und Ausführungszeit.
 +
<br><br>
 +
<b><font color="#FF0000">ACHTUNG!!!</font></b> Diese Funktion ist mit <u><b>array.binarysearch()</b></u> unnötig geworden! Bitte den Algorythmus wegen Performancegründen <b><font color="#FF0000">NICHT</font></b> auf Dauer nutzen und <b><u>nur für Lehrzwecke</u></b> einsetzten!
 +
<br><br>
 +
Der Search ist so programmiert, dass der Array nicht kopiert werden muß, sondern lediglich ein Speicherverweis dazu hergestellt wird. Das Array, welches als Quelle dient, wird dabei nicht verändert.
-
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.
+
==Die Syntax==
 +
 
 +
<b>BinarySearch</b> wird ganz einfach als <b>Methode</b> aufgerufen:
 +
 
 +
  BinarySearch(Verwendetes-Array,Länge-des-Array,Gesuchte-Zahl,SpeicherVariable);
 +
 
 +
Die Methode ist <b>VOID</b> da eine andere Umsetzung zum Entwicklungszeitpunkt (Version 0.1 Pre Alpha) nocht nicht zur Verfügung stand!
 +
 
 +
In der Variablen <b>SpeicherVariable</b> wird das Ergebnis, ein Wert <b>zwischen 0 und Länge-des-Array</b>, gespeichert.<br>
 +
Sollte die gesuchte Zahl <b>nicht gefunden</b> werden, ist <b>SpeicherVariable</b> nach der Verarbeitung <b>-1</b>!
 +
 
 +
<b>Hinweis:</b> Es wurde ein Workarround benötigt, da das Vergleichen der Ausdrücke zum Entwicklungszeitpunkt nur einzeln und mit <b>"<"</b> sowie <b>">"</b> möglich war!
==Der Algorythmus==
==Der Algorythmus==
Zeile 10: Zeile 27:
Der ganze Algorythmus ist als Methode verwirklicht worden. Dies ermöglicht die unveränderte übernahme des Quellcodes, siehe unten.
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){
+
function BinarySearch(ByRef a as array, aSe as integer) as integer {
-
      var i=0;
+
  var aG as integer;
-
      var tmp;
+
  var p1 as integer=0;
-
      While (++i<aLenght){
+
  var p2 as integer = a.Length;
-
        if (a[i-1]>a[i]){
+
-
            tmp=a[i-1];
+
  While(p1<p2){
-
            a[i-1]=a[i];
+
    aG=(p1+p2)/2;
-
            a[i]=tmp;
+
    if(a[aG]<aSe){p1=aG+1;}
-
            i=i-2;
+
    if(a[aG]>aSe){p2=aG;}
-
        }
+
    if(a[aG]=aSe){return aG}
-
        if(i<0){i=0}
+
-
      }
+
   }
   }
 +
 
 +
  return -1;
 +
}
==Der ultimative Test==
==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 aLaenge = 8;
+
var arr[] as integer = { 2, 9, 14, 16, 39, 48, 52, 70, 89, 94 };
-
  var arr[aLaenge] as integer = { 15, 2, 19, 8, 20, 8, 29, 4 };
+
var aSearch as integer = 29;
-
  WriteLine(' ');
+
var aGoal as integer = 0;
-
  WriteLine('Array vor der Sortierung:');
+
-
   WriteLine(arr[0] & ' ' & arr[1] & ' ' & arr[2] & ' ' & arr[3] & ' ' & arr[4] & ' ' & arr[5] & ' ' & arr[6] & ' ' & arr[7]);
+
WriteLine(' ');
-
  BubbleSort(arr,aLaenge);
+
-
  WriteLine(' ');
+
WriteLine('Suche nach Zahl ' & aSearch & '...');
-
   WriteLine('Array nach der Sortierung:');
+
aGoal = BinarySearch(arr, aSearch);
-
   WriteLine(arr[0] & ' ' & arr[1] & ' ' & arr[2] & ' ' & arr[3] & ' ' & arr[4] & ' ' & arr[5] & ' ' & arr[6] & ' ' & arr[7]);
+
-
  WriteLine(' ');
+
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 & '!');
 +
}
 +
WriteLine(' '); 
 +
 +
aSearch = 39
 +
 +
WriteLine('Suche nach Zahl ' & aSearch & '...');
 +
aGoal = BinarySearch(arr, aSearch);
 +
 +
if(aGoal<0){
 +
   WriteLine('Die gesuchte Zahl befindet sich nicht im angegebenen Array!');
 +
}
 +
else {
 +
   WriteLine('Die gesuchte Zahl ' & aSearch & ' befindet sich an Position ' & aGoal & '!');
 +
}
 +
WriteLine(' ');
==Der Erfolg==
==Der Erfolg==
Zeile 43: Zeile 80:
   Script gestartet.
   Script gestartet.
    
    
-
   Array vor der Sortierung:
+
   Suche nach Zahl 29...
-
   15 2 19 8 20 8 29 4
+
   Die gesuchte Zahl 29 befindet sich nicht im angegebenen Array!
    
    
-
   Array nach der Sortierung:
+
   Suche nach Zahl 39...
-
   2 4 8 8 15 19 20 29
+
   Die gesuchte Zahl 39 befindet sich an Position 4!
    
    
   Script beendet.
   Script beendet.
-
Viel Spaß mit BubbleSort!
+
<b>Anmerkung:</b> "Position 4" bedeutet natürlich Zahl 5, da für ein Array die Zahl 0 auch relevant ist. Es wird also ab 0 und nicht von 1 weg gezählt!
 +
 
 +
Viel Spaß mit BinarySearch!
MFG Proximo
MFG Proximo
 +
<br>
 +
<br>
 +
[[Kategorie:Methoden|BinarySearch]]

Aktuelle Version vom 21. April 2011, 18:38 Uhr

fertige Scripte | Anleitungen und FAQ | Überblick über die Scripting-Sektion | Hilfen zum Arbeiten im Wiki

Inhaltsverzeichnis

Der BinarySearch

Er wird verwendet um sortierte Arrays (z.B. mit BubbleSort vorsortiert) nach einer Zahl zu durchsuchen. BinarySearch ist erheblich schneller wie ein Linearer Search, spart Ressourcen sowie Rechen- und Ausführungszeit.

ACHTUNG!!! Diese Funktion ist mit array.binarysearch() unnötig geworden! Bitte den Algorythmus wegen Performancegründen NICHT auf Dauer nutzen und nur für Lehrzwecke einsetzten!

Der Search ist so programmiert, dass der Array nicht kopiert werden muß, sondern lediglich ein Speicherverweis dazu hergestellt wird. Das Array, welches als Quelle dient, wird dabei nicht verändert.

Die Syntax

BinarySearch wird ganz einfach als Methode aufgerufen: 

  BinarySearch(Verwendetes-Array,Länge-des-Array,Gesuchte-Zahl,SpeicherVariable);

Die Methode ist VOID da eine andere Umsetzung zum Entwicklungszeitpunkt (Version 0.1 Pre Alpha) nocht nicht zur Verfügung stand!

In der Variablen SpeicherVariable wird das Ergebnis, ein Wert zwischen 0 und Länge-des-Array, gespeichert.
Sollte die gesuchte Zahl nicht gefunden werden, ist SpeicherVariable nach der Verarbeitung -1!

Hinweis: Es wurde ein Workarround benötigt, da das Vergleichen der Ausdrücke zum Entwicklungszeitpunkt nur einzeln und mit "<" sowie ">" möglich war!

Der Algorythmus

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

function BinarySearch(ByRef a as array, aSe as integer) as integer {
  var aG as integer;
  var p1 as integer=0;
  var p2 as integer = a.Length;

  While(p1<p2){
    aG=(p1+p2)/2;
    if(a[aG]<aSe){p1=aG+1;}
    if(a[aG]>aSe){p2=aG;}
    if(a[aG]=aSe){return aG}
  }
 
  return -1;
}

Der ultimative Test

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

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

WriteLine(' ');

WriteLine('Suche nach Zahl ' & aSearch & '...');
aGoal = BinarySearch(arr, aSearch);

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 & '!');
}
WriteLine(' ');   

aSearch = 39

WriteLine('Suche nach Zahl ' & aSearch & '...');
aGoal = BinarySearch(arr, aSearch);

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

Der Erfolg

  Script gestartet.
  
  Suche nach Zahl 29...
  Die gesuchte Zahl 29 befindet sich nicht im angegebenen Array!
  
  Suche nach Zahl 39...
  Die gesuchte Zahl 39 befindet sich an Position 4!
  
  Script beendet.

Anmerkung: "Position 4" bedeutet natürlich Zahl 5, da für ein Array die Zahl 0 auch relevant ist. Es wird also ab 0 und nicht von 1 weg gezählt!

Viel Spaß mit BinarySearch!

MFG Proximo

Von „https://wiki.stne.net/index.php?title=Scripting:BinarySearch“
Persönliche Werkzeuge
Starflyer - Wikizeitung