de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Dynamic Binary Search

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Mehlhorn, K. (1979). Dynamic Binary Search. SIAM Journal on Computing, 8, 175-198.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AF76-5
##### Abstract
We consider search trees under time-varying access probabilities. Let $S = \{ B_1 , \cdots ,B_n \}$ and let $p_i^t$ be the number of accesses to object $B_i$ up to time $t$, $W^t = \sum {p_i^t }$. We introduce D-trees with the following properties.1) A search for $X = B_i$ at time $t$ takes time $O(\log W^t /p_i^t )$. This is nearly optimal.2) Update time after a search is at most proportional to search time, i.e. the overhead for administration is small.