Scripting:BinarySearch
Aus STNE-Wiki
Inhaltsverzeichnis |
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.
Die Syntax
BinarySearch wird ganz einfach als Methode aufgerufen:
BinarySearch(Verwendetes-Array,Länge-des-Array,Gesuchte-Zahl,Variable-zur-Speicherung-des-Ergebnisses);
Die Methode ist "VOID" da eine andere Umsetzung zum Entwicklungszeitpunkt (Version 0.1 Pre Alpha) nocht nicht zur Verfügung stand!
In der Variablen "Variable-zur-Speicherung-des-Ergebnisses" wird das Ergebnis, ein Wert zwischen "0" und "Länge-des-Array", gespeichert. Sollte die gesuchte Zahl nicht gefunden werden, ist "Variable-zur-Speicherung-des-Ergebnisses" nach der Verarbeitung "-1"!
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 & '...');
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 & '!');
}
WriteLine(' ');
aSearch = 39
WriteLine('Suche nach Zahl ' & aSearch & '...');
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 & '!');
}
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
