We consider the problem of finding an element of a given rank in a totally ordered set given in a read-only array, using limited extra storage cells. We give new algorithms for various ranges of extra space. Our upper bounds improve the previously known bounds in the range of space s such that s is o(lg~2n) and s>=clg lg n/lg lg lg n for some constant c. We also give faster algorithms to find small ranks.
展开▼
机译：我们考虑的问题是，使用有限的额外存储单元在只读数组中给定的完全有序集合中找到给定等级的元素。我们为各种范围的额外空间提供了新算法。我们的上限改善了空间s范围内的已知界限，使得s为o（lg〜2n），并且对于某些常数c，s> = clg lg n / lg lg lg n。我们还提供了更快的算法来查找较小的排名。
展开▼
