Struttura dei dati - Ricerca in interpolazione

La ricerca in interpolazione è una variante migliorata della ricerca binaria. Questo algoritmo di ricerca funziona sulla posizione di rilevamento del valore richiesto. Affinché questo algoritmo funzioni correttamente, la raccolta dei dati dovrebbe essere in una forma ordinata e distribuita equamente.

La ricerca binaria ha un enorme vantaggio in termini di complessità temporale rispetto alla ricerca lineare. La ricerca lineare ha la complessità nel caso peggiore di Ο (n) mentre la ricerca binaria ha Ο (log n).

Ci sono casi in cui la posizione dei dati di destinazione può essere nota in anticipo. Ad esempio, nel caso di un elenco telefonico, se vogliamo cercare il numero di telefono di Morphius. Qui, la ricerca lineare e anche la ricerca binaria sembreranno lente poiché possiamo saltare direttamente allo spazio di memoria in cui sono memorizzati i nomi che iniziano con "M".

Posizionamento nella ricerca binaria

Nella ricerca binaria, se i dati desiderati non vengono trovati, il resto dell'elenco viene diviso in due parti, inferiore e superiore. La ricerca viene eseguita in uno di essi.

Anche quando i dati vengono ordinati, la ricerca binaria non sfrutta i vantaggi per sondare la posizione dei dati desiderati.

Rilevamento della posizione nella ricerca in interpolazione

La ricerca per interpolazione trova un particolare elemento calcolando la posizione della sonda. Inizialmente, la posizione della sonda è la posizione dell'elemento più centrale della collezione.

Se si verifica una corrispondenza, viene restituito l'indice dell'articolo. Per dividere l'elenco in due parti, utilizziamo il seguente metodo:

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where −
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

Se l'elemento centrale è maggiore dell'elemento, la posizione della sonda viene nuovamente calcolata nel sotto-array a destra dell'elemento centrale. Altrimenti, l'elemento viene cercato nel sottoarray a sinistra dell'elemento centrale. Questo processo continua anche sul sottoarray finché la dimensione del sottoarray non si riduce a zero.

La complessità di runtime dell'algoritmo di ricerca di interpolazione è Ο(log (log n)) paragonato a Ο(log n) della BST in situazioni favorevoli.

Algoritmo

Poiché è un'improvvisazione dell'algoritmo BST esistente, stiamo menzionando i passaggi per cercare l'indice del valore dei dati 'target', utilizzando il rilevamento della posizione -

Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.

Pseudocodice

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

   Set Lo  →  0
   Set Mid → -1
   Set Hi  →  N-1

   While X does not match
   
      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if
      
      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo]) 

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else 
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure

Per conoscere l'implementazione della ricerca per interpolazione nel linguaggio di programmazione C, fare clic qui .