手指搜索数据结构
在数据结构上进行手指搜索被定义为该结构支持的任何搜索操作的扩展，其中对数据结构中元素的引用（手指）与查询一起给出。虽然最常将元素的搜索时间表示为数据结构中元素数量的函数，但将手指搜索时间视为元素和手指之间距离的函数。
在一组m个元素中，两个元素a和b之间的距离d(a,b)是它们的等级差。如果元素a和b是结构中的第i个和第j个最大元素，则等级差为| i-j |。如果在某些结构中进行常规搜索通常会消耗O（f(m)）时间，那么用手指元素b进行手指搜索元素a的理想情况下应该消耗O（f(d)）时间。请注意，由于d≤m，因此可以得出结论，在最坏的情况下，手指搜索与普通搜索一样糟糕。但是，实际上，这些退化的手指搜索比普通搜索执行更多的工作。例如，如果f(n)为log(n)，并且在最坏的情况下手指搜索的执行次数是普通搜索的两倍，那么当d>√n时手指搜索就会变慢。因此，
实作
一些流行的数据结构支持手指搜索，而无需对实际结构进行其他更改。在通过缩小可以找到a的间隔来执行元素a的搜索的结构中，从元素b进行手指搜索通常是通过从b反转搜索过程直到搜索间隔足够大以包含元素a来进行的正常搜索哪个点。
排序链表
在链表中，通常从一端到另一端以线性方式搜索元素。如果对链表进行了排序，并且对包含元素b的某个节点进行了引用，则可以通过从元素b开始搜索来在O(d)时间找到元素a。
排序数组
在排序数组B中，通常使用二进制搜索在B中搜索元素a。手指搜索是通过从B [j] = b实现单边搜索来执行的。二进制搜索在每次比较后将搜索空间减半，而单面搜索则在每次比较后将搜索空间加倍。具体而言，在单边搜索的第k次迭代（假设a> b）上，所考虑的间隔为B [j，j + 2 k-1 ]。B [j + 2 k-1 ]≥a时，扩展将立即停止，此时将对该间隔进行二进制搜索以查找元素a。如果单面搜索消耗k次迭代来查找包含元素a的间隔，则得出d> 2 k-2。二进制搜索该范围还将消耗另外的k次迭代。因此，手指从b搜索a消耗O(k)= O（log d）时间
。
跳过列表
在跳过列表中，只需从这一点继续进行搜索，即可从包含元素b的节点中手指搜索元素a。注意，如果a <b，则搜索沿反向进行；如果a> b，则搜索沿向前进行。向后的情况与跳过列表中的常规搜索对称，但向前的情况实际上更复杂。通常，由于列表开头的哨兵被认为是最高的节点，因此在跳过列表中的搜索预计会很快。但是，我们的手指可能是一个高度为1的节点。因此，我们在尝试搜索时可能很少攀爬；通常不会发生的事情。但是，即使有这种复杂性，我们也可以达到O（log d）期望的搜索时间。
挖土机
挖矿被定义为随机二叉树(BST)。搜索陷阱类似于在任何其他BST中搜索元素。但是，挖掘具有以下性质：两个距离元素之间的预期路径长度表示为O（log d）。因此，为了从包含元素b的节点中搜索元素a进行手指搜索，可以从b元素爬到树上，直到找到元素a的祖先为止，此时正常的BST搜索将以常规方式进行。在计算一个节点是否是另一个节点的祖先时，一个节点可能会扩充以支持这种形式的查询，以提供预期的O（log d）手指搜索时间。
绳索和树木
绳索（数据结构）的实现通常使用绳索位置迭代器访问字符串。迭代器可以看作是指向字符串某些特定字符的手指。像大多数平衡的树一样，当只给树的根时，绳索需要O（log(m)）时间来检索树的一片叶子中的数据。读取树的每片叶子似乎需要O（m * log(m)）时间。但是，通过存储一些额外的信息，可以实现迭代器以仅在O(1)时间内读取“下一个”叶子，而仅在O(m)时间内读取树的每个叶子。
以上是 手指搜索数据结构 的全部内容， 来源链接： utcz.com/z/316965.html
