On binary searching with non-uniform costs
On binary searching with non-uniform costs
复制标题
关于非均匀成本的二分搜索
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. Pessoa
中科院分区：
文献类型：
--
作者：
E. Laber;R. Milidiú;A. Pessoa
让我们考虑一个有序向量A[1：n]。如果测试每个位置的成本是相似的，那么标准的二分搜索是搜索向量的最佳策略。在平均和最坏的情况下都是如此。然而，如果成本是不均匀的，那么最好的策略不一定是标准的二分搜索。最好的算法，以构建一个战略，使预期的搜索成本最小化运行在（n3）的时间和需要（n2）的空间。同样的复杂性适用于最佳算法，以构建最小化最坏情况搜索成本的策略。
在这里，我们展示了如何有效地构建搜索策略，最多是一个常数的因素，从最佳的。这些构造采用线性时间，只使用线性空间。对于极小化期望搜索代价的问题，我们提出了一个算法，该算法需要（n）空间，并且对于任意固定的∈ > 0，在（n）时间内给出（2 + ∈ +（1））-近似解.另一方面，对于最坏情况搜索代价最小化问题，我们描述了一个算法，该算法需要（n）空间，并在（n）时间内给出（2 + ∈ +（1））-近似解，对于任何固定值∈ > 0。这两个问题出现在处理由后缀数组索引的分布式文本数据库中的查询时。
Let us consider an ordered vector A[1 : n]. If the cost of testing each position is similar, then the standard binary search is the best strategy to search the vector. This is true in both average and worst case. However, if the costs are non-uniform, then the best strategy is not necessarily the standard binary search. The best algorithm to construct a strategy that minimizes the expected search cost runs in &Ogr;(n3) time and requires &Ogr;(n2) space. The same complexities hold for the best algorithm to construct a strategy that minimizes the worst case search cost.
Here, we show how to efficiently construct search strategies that are at most at a constant factor from the optimal one. These constructions take linear time and use only linear space. For the problem of minimizing the expected search cost, we present an algorithm that requires &Ogr;(n) space and gives a (2 + ∈ + &Ogr;(1))-approximated solution in &Ogr;(n) time, for any fixed value of ∈ > 0. On the other hand, for the problem of minimizing the worst case search cost, we describe an algorithm that requires &Ogr;(n) space and gives a (2 + ∈ + &Ogr;(1))- approximated solution in &Ogr;(n) time, for any fixed value of ∈ > 0. These two problems arise when processing a query in a distributed text database indexed by a suffix array.