Sortierverfahren
Hier sind zwei Varianten des Binärsuch-Verfahrens,
hoffentlich hilfreich für die Klausur am 6. Mai:
/** Binärsuch-Methode von Benny
* @param Search_in Dieser Array enthält die bereits sortierten Daten
* die durchsucht werden sollen.
* @param to_Search enthält den Wert der in Search_in gesucht werden soll.
* @return Die Stelle im Array an der sich der gesuchte Wert befindet. */
public static int Quicksearch(int[] Search_in,int to_Search)
{
int curindex = (Search_in.length)/2;
// momentanes Feld im Array das überprüft wird!
int sexymama = curindex // Hilfsvariable die angibt, um wieviele
// Felder curindex verschoben werden muss!
boolean end = false; // gibt an ob die Suche fertig ist
if (sexymama % 2 == 1) { sexymama++;} // wenn die zahl ungerade ist wird sie
//um 1 erhöht damit beim Teilen keine ungenauen Werte durch Kürzen entstehen
while (end == false) // While-Schleife
{
if (Search_in[curindex] == to_Search)
{end = true;} // überprüft ob die Suche fertig ist.
if (Search_in[curindex] > to_Search)
{sexymama = sexymama / 2; curindex = curindex - (int)sexymama;}
// wenn der Wert zu groß ist wird auf die Mitte der linken Hälfte
// verschoben. Dies geschieht dadurch dass die Hilfsvariable vorher immer
// durch 2 geteilt wird. Dadurch enthält sie immer dejenigen Wert, um den
// curindex erhöht oder erniedrigt werden muss.
if (Search_in[curindex] < to_Search)
{sexymama = sexymama / 2; curindex = curindex + (int)sexymama;} // s.o.
}
return curindex;
}
/** Binärsuch-Methode von Vladimir T.
* @param z die zu suchende Zahl
* @param array der nach z zu durchsuchende Array
* @param L linker Rand des zu durchsuchenden Bereichs
* @param R rechter Rand des zu durchsuchenden Bereichs
* @return Stelle, an der z vorkommt oder -1 falls nicht */
private static int binstest(int z, int[] array, int L,int R)
{//Prüfung ob die Menge keine Elemente enthaelt
if (array.length == 0) {return -1;}
else {return bins(z,array,L,R);}
}
/** Quicksearch-Methode von Vladimit T.
* Sucht eine Zahl namens "z" in einem Array namens "array"
* wobei dieser die Mindestlänge 1 hat.
* @param z die zu suchende Zahl
* @param array der nach z zu durchsuchende Array
* @param L linker Rand des zu durchsuchenden Bereichs
* @param R rechter Rand des zu durchsuchenden Bereichs
* @return Stelle, an der z vorkommt oder -1 falls nicht */
private static int bins(int z, int[] array, int L,int R)
{//Programmcode
if (L==R) //wenn es nur ein Element gibt...
{ //...vergleiche, ob dieses Element gesucht wurde
if (z == array[L]) {return L+1;} //Stelle des gesuchten Elements
else {return -1;} //Element nicht gefunden
}
else
{ //m-Initialisierung
int m = (R+L)/2; //mittleren Wert bestimmen
if (array[m] >= z) {return bins(z,array,L,m);} //Suche, ob z links...
else {return bins(z,array,(1+m),R);} //...oder rechts von m liegt
}
}
BinarySearchVariationen.java (3 kByte)anzeigen - speichern
Datei wurde schon 72-mal heruntergeladen.
