Ricerca in interpolazione in Java

1. Introduzione

In questo tutorial, esamineremo gli algoritmi di ricerca per interpolazione e discuteremo i loro pro e contro. Inoltre, lo implementeremo in Java e parleremo della complessità temporale dell'algoritmo.

2. Motivazione

La ricerca per interpolazione è un miglioramento rispetto alla ricerca binaria su misura per dati distribuiti in modo uniforme.

La ricerca binaria dimezza lo spazio di ricerca in ogni passaggio indipendentemente dalla distribuzione dei dati, quindi la complessità temporale è sempre O (log (n)) .

D'altra parte, la complessità del tempo di ricerca dell'interpolazione varia a seconda della distribuzione dei dati . È più veloce della ricerca binaria di dati distribuiti uniformemente con la complessità temporale di O (log (log (n))) . Tuttavia, nello scenario peggiore, può avere prestazioni scadenti come O (n) .

3. Ricerca in interpolazione

Simile alla ricerca binaria, la ricerca per interpolazione può funzionare solo su un array ordinato. Posiziona una sonda in una posizione calcolata a ogni iterazione. Se la sonda è proprio sull'articolo che stiamo cercando, verrà restituita la posizione; altrimenti, lo spazio di ricerca sarà limitato al lato destro o sinistro della sonda.

Il calcolo della posizione della sonda è l'unica differenza tra la ricerca binaria e la ricerca per interpolazione.

Nella ricerca binaria, la posizione della sonda è sempre l'elemento più centrale dello spazio di ricerca rimanente.

Al contrario, la ricerca per interpolazione calcola la posizione della sonda in base a questa formula:

Diamo un'occhiata a ciascuno dei termini:

  • sonda : a questo parametro verrà assegnata la nuova posizione della sonda.
  • lowEnd : l'indice dell'elemento più a sinistra nello spazio di ricerca corrente.
  • highEnd : l'indice dell'elemento più a destra nello spazio di ricerca corrente.
  • data [] : l'array contenente lo spazio di ricerca originale.
  • articolo : l'articolo che stiamo cercando.

Per capire meglio come funziona la ricerca per interpolazione, dimostriamolo con un esempio.

Supponiamo di voler trovare la posizione di 84 nella matrice seguente:

La lunghezza dell'array è 8, quindi inizialmente highEnd = 7 e lowEnd = 0 (perché l'indice dell'array inizia da 0, non da 1).

Nella prima fase, la formula della posizione della sonda risulterà in sonda = 5:

Poiché 84 (l' elemento che stiamo cercando) è maggiore di 73 (l' elemento della posizione della sonda corrente ), il passaggio successivo abbandonerà il lato sinistro dell'array assegnando lowEnd = probe + 1. Ora lo spazio di ricerca consiste solo di 84 e 101. La formula della posizione della sonda imposterà la sonda = 6 che è esattamente l'indice di 84:

Poiché l'oggetto che stavamo cercando è stato trovato, verrà restituita la posizione 6.

4. Implementazione in Java

Ora che abbiamo capito come funziona l'algoritmo, implementiamolo in Java.

Per prima cosa inizializziamo lowEnd e highEnd :

int highEnd = (data.length - 1); int lowEnd = 0;

Successivamente, impostiamo un ciclo e in ogni iterazione calcoliamo la nuova sonda in base alla formula di cui sopra. La condizione del ciclo assicura che non siamo fuori dallo spazio di ricerca confrontando l' elemento con i dati [lowEnd] e i dati [highEnd] :

while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); }

Controlliamo anche se abbiamo trovato l'elemento dopo ogni nuova assegnazione della sonda .

Infine, regoliamo lowEnd o highEnd per diminuire lo spazio di ricerca ad ogni iterazione:

public int interpolationSearch(int[] data, int item) { int highEnd = (data.length - 1); int lowEnd = 0; while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) { int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]); if (highEnd == lowEnd) { if (data[lowEnd] == item) { return lowEnd; } else { return -1; } } if (data[probe] == item) { return probe; } if (data[probe] < item) { lowEnd = probe + 1; } else { highEnd = probe - 1; } } return -1; }

5. conclusione

In questo articolo, abbiamo esplorato la ricerca in interpolazione con un esempio. L'abbiamo implementato anche in Java.

Gli esempi mostrati in questo tutorial sono disponibili su Github.