Das einzigartige Forum
allrounder

124c4u · Erstellt: 04.05.08, 18:13 Betreff: 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
}
}

vovan1 · Moderator Beiträge: 240

Kleine Korekture,dass von Benny hat *(Benny nimm das nicht persönlich )ein Paar Maken,
benutzt mal die von Vladimir T. oder diese aus der "Standard Java Bibliothek".

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;

while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];

if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}

Naja meine ist auch nicht schlecht xD

Was dich nicht umbringt,
Macht dich nur noch Stärker.

Proffessor.Dr.Drewer

124c4u · Erstellt: 05.05.08, 13:40 Betreff: Re: Sortierverfahren

Einfach nur "Macken" behaupten ist leicht - Was genau ist bei Bennys Methode nicht korrekt?
In der Arbeit morgen zählen für solche Aufgabenstellungen auch nur konkrete Gegenbeispiele.
(Damit will ich nicht sagen, dass Bennys Weg korrekt oder gar perfekt ist, aber bevor man eine neue Methode vorschlägt sollte man wissen, was an der alten Variante verbesserungsbedürftig ist.)

Bei der Methode aus der Standardbibliothek muss man sich klar sein, was ">>>" bedeutet (nämlich ein binäres Nach-rechts-Schieben der Bits, also eine elegante Methode um schnell durch zwei zu dividieren) und wieso (anstelle einer RuntimeException oder einer -1 wie bei uns) der negative Wert -(low+1) zurückgegeben wird (diesen Grund verrate ich noch nicht).

P.S. Zum Motto von "Proffessor.Dr.Drewer": Bedeutet das, dass ein "Ungenügend" in Informatik jemanden stärker macht? ;-)