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!

  1.  Suche nach einem Wert 5 of 7 tests passing
  2. Die Methode 
  3. int search(int[] sortedData, int value, Result result)
  4.  soll mittels binärer Suche nach dem Index vom übergebenen Wert suchen.
  5. 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.
  6. 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;
}
Bild zum Beitrag
Java, Programmiersprache, Algorithmus, binary

Meistgelesene Fragen zum Thema Java