Ist es möglich, eine Interpolationssuche durchzuführen, um einen festen Punkt in einem Array zu finden?

Question

In einem sortierten Array mit keine Duplikate Werte, können wir die Interpolationssuche verwenden, um zu finden, ob es einen festen Punkt in einem Array wie Array [i] == i?

der Code für die Interpolation Suche Dies ist:

public static int interpolationSearch(int[] array, int x) { 
if (array == null || array.length==0) { 
     return; 
} 

    int low = 0; 
    int high = array.length - 1; 
    int mid; 

    while (array[low] != array[high] && x >= array[low] && x <= array[high]) { 
     mid = low + ((x - array[low]) * (high - low)/(array[high] - array[low])); 

     if (array[mid] < x) 
      low = mid + 1; 
     else if (x < array[mid]) 
      high = mid - 1; 
     else 
      return mid; 
    } 

    if (x == array[low]) 
     return low ; 
    else 
     return -1; 
} 

ich oft finden, dass wir die binäre Suche in einem Array verwenden, um einen festen Punkt zu finden, die es in O (log (n)) getan . Aber da die Interpolationssuche "nur" eine verbesserte Version der binären Suche ist, ist es theoretisch möglich, sie zu verwenden, um diesen Punkt zu finden? Ich versuchte naiv, x im obigen Code und in der Interpolationsformel zu entfernen, aber es liefert nicht immer das korrekte Ergebnis. Ich weiß nicht, ob es eine andere Beziehung dafür gibt oder ob wir es wirklich mit Interpolation machen können.

Answer 1

Angenommen, Sie haben ein Array von ganzen Zahlen ohne Duplikate, ja, Sie können dies tun. Der Grund dafür ist, dass, wenn A ein sortiertes Array von ganzen Zahlen ist, das neue Array B, das durch B [i] = A [i] - i gegeben ist, ebenfalls sortiert ist, so dass Interpolationssortierung darauf angewendet werden kann.

Dies gilt jedoch im Allgemeinen nicht für Arrays von nicht ganzzahligen Werten. Betrachten Sie beispielsweise das Array A = [0, 0.5, 3], das in aufsteigender Reihenfolge sortiert ist. Dann ist B = [0, -0.5, 1] ​​nicht sortiert.

Es ist wahrscheinlich ein Fehler irgendwo in Ihrem Code, wenn dies nicht richtig funktioniert.