Sortierte Liste nach Wert durchsuchen

[Maria80]

Hallo zusammen!
Ich hab eine Frage zum effektiven Sortieren von einem Feld.
Das Feld ist aufsteigend sortiert.

Public static int findeDenBuchstaben(int [ ] sortierteListe, int Buchstabe){

int i=-1;

//schellste Lösung um den Buchstaben in dem sortierten Feld zu finden

Return i;
}

Geht das eventuell durch mehrmaliges Auftrennen der Liste? (log)?
Danke euch!

 

[Maria80]

Sorry ich meinte nicht zum Sortieren, sondern zum Suchen des Buchstaben in dem sortierten Feld.
Und dann Rückgabe der Position in der der Buchstabe gefunden wurde..
wenns den buchstaben nicht gibt return -1;
dankeschön..

 

[The_S]

Wenn das Feld sortiert ist:

Arrays#binarySearch

 

[Kim Stebel]

mitleres element nehmen und vergleichen:
gleich? gefunden!
kleiner als gesucht? wiederholen mit "oberer" hälfte des arrays.
größer als gesucht? wiederholen mit "unterer" hälfte des arrays.
zeitkomplexität ist log(n).

noch fragen?

 

[Maria80]

Erstmal lieben Dank.
Ja hab noch einge Fragen:
z.B. wie sieht der Code aus?????

Wie komme ich an das mittlere Element.
Wie trenne ich die Liste weiter auf?
Anfänger Habt Verständnis..

 

[The_S]

Was spricht gegen Arrays#binarySearch?

 

[Kim Stebel]

@hobbit: ich denke mal sie will wissen, wie es funktioniert, statt sich nur auf die std-libs zu verlassen.

@maria: durch lesen lernst du nicht besonders viel. versuch es doch mal selber zu schreiben.
ein paar tips:
das mittlere element? sortierteListe[sortierteListe.length/2]
auftrennen? nicht nötig, einfach anfang und ende der "neuen" liste als parameter übergeben. die mitte kannst du dann einfach bestimmen als (anfang + ende) / 2

 

[Gast]

Hab dazu das hier gefunden:

public static int binarySearch( Comparable [ ] a, Comparable x )
{
int low = 0;
int high = a.length - 1;
int mid;

while( low <= high )
{
mid = ( low + high ) / 2;

if( a[ mid ].compareTo( x ) < 0 )
low = mid + 1;
else if( a[ mid ].compareTo( x ) > 0 )
high = mid - 1;
else
return mid;
}

return NOT_FOUND; // NOT_FOUND = -1
}


Das Feld ist vom Typ Comparable, aber ich brauche doch ein intFeld....Kann ich Comparable durch int ersetzen?

 

[SlaterB]

kannst du es ausprobieren und die Antwort selber posten? ( a[ mid ].compareTo( x ) sieht für ints natürlich anders aus)