Flexible interpolated-binary search over sorted sets

Bonasera, B.; Pagano, F.; Provetti, A.

IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

We revisit the classical algorithms for searching over sorted sets and introduce a new algorithm, called adaptive search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Insertion sort, only a constant number of extra comparisons is introduced. Yet, under several relevant input data distributions our algorithm shows average case cost comparable to that of Interpolation Search, i.e., O(log log n) while the worst case cost is always in O(log n), as with Binary search. This result compares well with the traditional result of Santoro and Sidney Interpolation-Binary Search and the recent approach of Demaine et al. on searching non-independent data.

Flexible interpolated-binary search over sorted sets / B. Bonasera, F. Pagano, A. Provetti. ((Intervento presentato al convegno Italian Conference on Theoretical Computer Science (ICTCS) tenutosi a Cremona nel 2009.

Titolo:	Flexible interpolated-binary search over sorted sets
Autori:	B. Bonasera PAGANO, FRANCESCO (Secondo) PROVETTI, ALESSANDRO (Ultimo) mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	set-2009
Parole Chiave:	sorting ; sorted-sets
Settore Scientifico Disciplinare:	Settore INF/01 - Informatica
Enti collegati al convegno:	Politecnico di Milano
Tipologia:	Conference Object
Citazione:	Flexible interpolated-binary search over sorted sets / B. Bonasera, F. Pagano, A. Provetti. ((Intervento presentato al convegno Italian Conference on Theoretical Computer Science (ICTCS) tenutosi a Cremona nel 2009.
Appare nelle tipologie:	14 - Intervento a convegno non pubblicato

File in questo prodotto:

File	Descrizione	Tipologia	Licenza
ictcs2009.pdf		Publisher's version/PDF		Open Access Visualizza/Apri

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/2434/148238

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.