File InterpolationSearch.h

↰ Parent directory (ADS/search)

The search by interpolation of section 12.1 in a sorted vector of numbers: in the part A[ i .

Definition (ADS/search/InterpolationSearch.h)

Detailed Description

. j ] the key v is looked for in the place :math:`[

m = i + leftlfloor ( j - i ) frac{v - A[ i ]}{A[ j ] - A[ i ]} rightrfloor

` instead of the middle one, as one opens a phone book near its start to look for a name in C. With keys uniformly distributed it takes :math:` O( log log n ) ` expected time, but O( n ) in the worst case, so that with few keys or with keys not uniform the binary search is better. The search stops when v is out of [ A[ i ] , A[ j ] ], and probes A[ i ] when A[ i ] = A[ j ]. The fraction is computed in double, and when it is undefined, i.e., 0 / 0 for distinct keys equal as doubles (integers past 2^53) or inf / inf for infinite keys, the probe is the middle place.

The contracts [see File Contract.h]: the vector must be sorted, an audit checked at the level 3, and a miss is checked against a linear scan. The functions are defined in InterpolationSearch.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 12.1, https://algoritmicamente.it/materiali/libro/capitoli/cap12.pdf

  1. Perl, A. Itai, H. Avni, Interpolation search: a log log N search, Communications of the ACM 21(7), 550-553, 1978, doi:10.1145/359545.359557

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions