Interpolation search: differenze tra le versioni

Versione delle 13:09, 24 giu 2017

Versione delle 20:07, 21 nov 2020

Riga 21:

Il seguente codice [[C++]] è un esempio di semplice implementazione. Ad ogni passo calcola una possibile posizione del valore, per poi restringere l'intervallo —come nella ricerca binaria— aumentando il lower bound o diminuendo l'upper bound.

<sourcesyntaxhighlight lang="cpp">

template <typename T>

int interpolation_search(T arr[], int size, T key)

Riga 44:

return -1;

}

</syntaxhighlight>

</source>

<!-- Notice that having probed the list at index ''mid'', for reasons of loop control administration, this code sets either ''high'' or ''low'' to be not ''mid'' but an adjacent index, which ___location is then probed during the next iteration. Since an adjacent entry's value will not be much different the interpolation calculation is not much improved by this one step adjustment, at the cost of an additional reference to distant memory such as disc.