Name
Abstract | ||
|---|---|---|
Let us consider an ordered set of keys A = {a1 ... an}, where the probability of searching ai is 1/n, for i = 1,..., n. If the cost of testing each key is similar, then the standard binary search is the strategy with minimum expected access cost. However, if the cost of testing ai is ci, for i = 1 .... , n, then the standard binary search is not necessarily the best strategy.In this paper, we prove that the expected access cost of an optimal search strategy is bounded above by 4Cln(n + 1)/n, where C= Σi=1n ci . Furthermore, we show that this upper bound is asymptotically tight up to constant factors. The proof of this upper bound is constructive and generates a 4ln(n + 1)-approximated algorithm for constructing near-optimal search strategies. This algorithm runs in O(n2) time and requires O(n) space, which can be useful for practical cases, since the best known exact algorithm for this problem runs in O(n3) time and requires O(n2) space. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0304-3975(01)00262-6 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
different access cost,constant factor,near-optimal search strategy,standard binary search,approximated algorithm,optimal search strategy,expected access cost,best strategy,minimum expected access cost,keys A,exact algorithm | Journal | 287 |
Issue | ISSN | Citations |
2 | Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.34 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eduardo Sany Laber | 1 | 229 | 27.12 |
| Ruy Luiz Milidiú | 2 | 192 | 20.18 |
| Artur Alves Pessoa | 3 | 270 | 24.30 |