Binärer Suchalgorithmus - wo liegt der Fehler?
Hallo liebe Community,
ich arbeite an einem Suchalgorithmus, der in einer sortierten Liste das Element finden soll, das einem gegebenen Wert am nächsten liegt. Trotz ausführlicher Tests mit über 100 Edge Cases, die alle fehlerfrei terminiert haben, liegt noch ein Fehler im Code. Bisher konnte ich jedoch keinen Fall finden, der nicht korrekt funktioniert.
Kann jemand von euch vielleicht einen Blick darauf werfen und mir helfen, mögliche Schwachstellen oder Fehler zu identifizieren? Ich wäre für jeden Tipp oder Testfall, der mein Problem offenlegen könnte, sehr dankbar!
- Suche nach einem Wert 5 of 7 tests passing
- Die Methode
int search(int[] sortedData, int value, Result result)- soll mittels binärer Suche nach dem Index vom übergebenen Wert suchen.
- Dabei wird immer der mittlere Wert vom Suchbereich angesehen. Falls dies der gesuchte Wert ist, kann dessen Index zurück gegeben werden. Ansonsten verkleinert sich der Suchbereich auf die Indices, in denen der gesuchte Wert noch liegen kann. Falls der Suchbereich nur noch einen Wert enthält, soll ebenfalls abgebrochen werden.
- Wenn der Wert nicht im Array enthalten ist, soll stattdessen der Index vom nächst größeren oder nächst kleineren Wert zurückgegeben werden. Welcher der beiden Indices ist dabei egal, solange der zurückgegebene Index im Array liegt.
Code:
public static int search(int[] sortedData, int value, Result result) {
int left = 0;
int right = sortedData.length - 1;
int nearestindex = -1;
int currentSmallest = Integer.MAX_VALUE;
while(left <= right) {
int middle = left + (right - left) / 2;
int difference = Math.abs(value - sortedData[middle]);
if(difference < currentSmallest) {
currentSmallest = difference;
nearestindex = middle;
} else if(difference == currentSmallest) {
if(Math.abs(value - nearestindex) > Math.abs(value - middle)) {
nearestindex = middle;
}
}
result.addStep(middle);
if(sortedData[middle] == value) {
return middle;
}
if (sortedData[middle] < value) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return nearestindex;
}
4 Antworten
while(left <= right) {
Du hörst erst auf, wenn das Intervall leer ist. Ich hätte erwartet, dass die Suche zu Ende ist, wenn zwei benachbarte Werte l, r mit l≤value≤r gefunden wurden.
int middle = left + (right - left) / 2;
int difference = Math.abs(value - sortedData[middle]);
if(difference < currentSmallest) {
Wozu diese Abfrage? In einem sortierten Array kann doch difference>currentSmallest gar nicht passieren.
currentSmallest = difference;
nearestindex = middle;
Wieso middle? Könnte bei middle+1 oder middle-1 nicht ein besserer Wert stehen? Ich bin mir nicht sicher, ob das im nächsten Durchlauf (falls es noch einen gibt) repariert wird.
if(Math.abs(value - nearestindex) > Math.abs(value - middle)) {
Das ist gruselig. Bei hinreichend großem value testest Du nearestindex<middle (was auch immer das bezwecken soll). Wenn value kleiner als die betrachteten Indizes ist, testest Du nearestindex>middle. Und bei einem value dazwischen passieren seltsame Dinge.
Besonders schräg wird diese Sache dadurch, dass nearestindex=middle in nächsten Durchlauf garantiert außerhalb des Intervalls liegt, weil Du ja entweder vor oder hinter middle weitersuchst.
Ich denke, Du hast Dir mit dem Tracken der Differenz einen Knoten ins Hirn gemacht. Implementiere einfach eine Intervallschachtelung bis runter zur Intervalllänge ≤2, und gib dann die bessere Grenze zurück.
Vergiss nicht zu prüfen, ob die Sonderfälle value<sortedData[0] und value>sortedData[len-1] sauber durchlaufen. Falls nicht, musst Du das getrennt abbacken.
Ich verstehe nicht, warum Du nciht einfach bei erfolgloser Suche let oder right zurückgibst.
. Welcher der beiden Indices ist dabei egal, solange der zurückgegebene Index im Array liegt.
10 90 100 200 300
gesucht 80.
Lasse Dir von Deinem Algo mal ein Debug Output aller Werte machen ;-).
> Task :BinSea.main()
added step to index 2
added step to index 0
added step to index 1
1
korrekter Output.
Ah, hatte vergessen, daß Du erst bei left>right abbrichst und nochmal die Position wechselst.
Dann gibt es im Endeffekt nur noch eien Möglichkeit: Nimm die Testvektoren der failign Tests und vergleiche Deine Ausgabe mit dem vom Test erwarteten.
Genau hier liegt mein Problem. Welche Tests fehlschlagen, wird nicht angezeigt. Es wird lediglich die Fehlermeldung geteilt, dass für einige der Tests falsche Indizes zurückgegeben wurden - weitere Informationen werden nicht geteilt.
Du aktualisiert nearestindex basierend auf der Bedingung difference < currentSmallest. Dies sieht korrekt aus, aber die darauf folgende Bedingung (else if (difference == currentSmallest)) könnte Probleme verursachen. Die innere Bedingung vergleicht Math.abs(value - nearestindex) mit Math.abs(value - middle), was inkorrekt ist, da nearestindex ein Index und kein Wert aus sortedData ist. Die korrekte Implementierung sollte Math.abs(value - sortedData[nearestindex]) sein.
else if (difference == currentSmallest) {
if(Math.abs(value - sortedData[nearestindex]) > Math.abs(value - sortedData[middle])) {
nearestindex = middle;
}
}
Das stimmt, habe ich ausgebessert, löst jedoch weiterhin nicht die fehlgeschlagenen Testcases.
Du hast vergessen, zu prüfen, ob der benachbarte Wert auch tatsächlich näher am gesuchten Wert liegt oder vielleicht der erste gefundene Wert schon der am nächsten liegende ist.
Bei einer erfolglosen Suche left oder right zurückzugeben, wäre ungenau, da diese Indizes am Ende der Suche oft auf Positionen zeigen, die nicht den nächstgelegenen Wert zum gesuchten Wert enthalten.