データ構造での指検索

データ構造のフィンガー検索は、構造がサポートする検索操作の拡張として定義され、データ構造内の要素への参照（フィンガー）がクエリとともに指定されます。要素の検索時間は、データ構造内の要素数の関数として最も頻繁に示されますが、指の検索時間は、要素と指の間の距離の関数として扱われます。

m個の要素のセットでは、2つの要素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）であり、最悪の場合、フィンガーサーチが通常のサーチの2倍の比較を実行する場合、d>√nの場合、フィンガーサーチは遅くなります。したがって、指の検索は、ターゲットが実際に指に近いと合理的に予想できる場合にのみ実装する必要があります。

実装

一部の一般的なデータ構造は、実際の構造に追加の変更を加えることなく、フィンガー検索をサポートしています。要素aの検索が、aを見つけることができる間隔を絞り込むことによって実行される構造では、要素bからの指検索は、通常、検索間隔が要素aを含むのに十分な大きさになるまで、検索プロセスをbから逆にすることによって実行されます。どのポイントの検索が通常どおり進行します。

ソートされたリンクリスト

リンクリストでは、通常、一方の端からもう一方の端までトラバースすることにより、要素を直線的に検索します。リンクリストがソートされていて、要素bを含むノードへの参照がある場合、要素bから検索を開始することにより、O（d）時間で要素aを見つけることができます。

ソートされた配列

ソートされた配列Bでは、通常、バイナリ検索を使用してB内の要素aを検索します。フィンガーサーチは、B [j]=bから片側サーチを実装することによって実行されます。二分探索は各比較後に探索空間を半分にしますが、片側探索は各比較後に探索空間を2倍にします。具体的には、片側検索のk回目の反復（a> bと仮定）で、検討中の間隔はB [j、j + 2 ^k-1 ]。 B [j + 2 ^k-1 になるとすぐに拡張が停止します ]≥a、この時点でこの間隔は要素aをバイナリ検索します。片側検索が要素aを含む区間を見つけるためにk回の反復を消費する場合、d> 2 ^k-2 となります。 。この範囲を二分探索すると、さらにk回の反復が必要になります。したがって、bからaを指で検索すると、O（k）=O（log d）時間がかかります

。

スキップリスト

スキップリストでは、このポイントから検索を続行するだけで、要素bを含むノードから要素aを指で検索できます。 a bの場合、検索は順方向に進むことに注意してください。後方の場合はスキップリストでの通常の検索と対称的ですが、前方の場合は実際にはもっと複雑です。通常、スキップリストでの検索は、リストの先頭にある番兵が最も高いノードと見なされるため、高速であると予想されます。ただし、指は高さ1のノードである可能性があります。このため、検索中に登ることはめったにありません。通常は発生しない何か。ただし、この複雑さがあっても、O（log d）の予想検索時間を達成できます。

Treaps

Treapは、ランダム化された二分探索木（BST）として定義されます。 Treapでの検索は、他のBSTでの要素の検索と似ています。ただし、Treapには、distanceの2つの要素間の予想パス長がO（log d）として示されるという特性があります。したがって、要素bを含むノードから要素aを指で検索するには、要素aの祖先が見つかるまで、b要素からツリーに登ることができます。その時点で、通常のBST検索が通常どおりに進行します。ノードが別のノードの祖先であるかどうかを計算するのは簡単ではありませんが、このフォームのクエリをサポートするようにツリーを拡張して、予想されるO（log d）フィンガー検索時間を提供することができます。

ロープと木

ロープ（データ構造）の実装では、通常、コード位置イテレータを使用して文字列にアクセスします。イテレータは、文字列の特定の文字を指す指と見なすことができます。ほとんどのバランスの取れたツリーと同様に、ロープは、ツリーのルートのみが指定されている場合、ツリーの1つのリーフでデータを取得するためにO（log（m））時間を必要とします。ツリーのすべての葉を読み取るには、O（m * log（m））時間が必要なようです。ただし、少し余分な情報を格納することで、イテレータを実装して、「次の」リーフをO（1）時間だけで読み取り、ツリーのすべてのリーフをO（m）時間だけで読み取ることができます。