Was ist falsch an meiner Implementierung eines Interpolationssuchalgorithmus?

Question

Also habe ich eine Implementierung eines Interpolations-Such-Algorithmus in Java hier bekam:

public static boolean search(int key, int[] array) { 
    int low = 0, high = array.length - 1; 
    int middle = -1; 

    while(low <= high) { 
     middle = low + (((high - low)/(array[high] - array[low])) * (key - array[low])); 
     if(array[middle] == key) 
      return true; 
     else { 
      if(array[middle] < key) 
       low = middle + 1; 
      else 
       high = middle - 1; 
     } 
    } 
    return false; 
} 

Es ist für Werte des im Array-Bereich arbeitet, immer wahr Rückkehr, aber für Werte außerhalb des Bereichs meiner Arrays es nicht funktioniert (dh wenn ich eine Liste von Elementen von 1 bis 15 habe, funktionieren die Werte 0 und 16 nicht, da ich eine ArrayIndexOutOfBoundsException bekomme).

Ich kann nicht scheinen, aus dem Debugger herauszufinden, wo ich falsch liege.

Danke!

Answer 1

Das Problem ist, dass die key Variable die middle für die Berechnung verwendet wird, damit es validiert werden muss, bevor die Schleife überprüft werden, ob sie niedriger ist als der niedrigste Wert und höher als der höhere Wert im Array:

while((array[high] != array[low] && key >= array[low] && key <= array[high]))

Wenn die Aussage falsch ist, dann gibt es keine Notwendigkeit, innerhalb der Schleife zu gehen, weil man von vornherein weiß, dass der Schlüssel nicht innerhalb des Arrays ist (da das Array sortiert ist).

Überprüfen Sie auch die Implementierung auf Wikipedia.