# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Dynamic Binary Search

##### 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.