資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究資料結構中的手指搜尋
資料結構上的手指搜尋被定義為該結構支援的任何搜尋操作的擴充套件，其中給定資料結構中一個元素的引用（手指）以及查詢。雖然元素的搜尋時間最常表示為資料結構中元素數量的函式，但手指搜尋時間被視為元素與手指之間距離的函式。
在一組 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+2k-1]。當 B[j + 2k-1] ≥ a 時，擴充套件停止，此時對該區間進行二分查詢以查詢元素 a。如果單邊搜尋消耗 k 次迭代來找到包含元素 a 的區間，則 d > 2k-2。對該範圍進行二分查詢也將消耗另外 k 次迭代。因此，從 b 對 a 進行手指搜尋消耗 O(k) = O(log d) 時間
.
跳錶
在跳錶中，可以透過簡單地從該點繼續搜尋，從包含元素 b 的節點對元素 a 進行手指搜尋。請注意，如果 a < b，則搜尋向後進行，如果 a > b，則搜尋向前進行。向後案例與跳錶中的普通搜尋對稱，但向前案例實際上更復雜。通常，跳錶中的搜尋預計會很快，因為列表開頭的哨兵被認為是最高的節點。但是，我們的手指可能是一個高度為 1 的節點。因此，在嘗試搜尋時，我們可能很少攀升；這在正常情況下永遠不會發生。但是，即使存在這種複雜情況，我們也可以實現 O(log d) 的預期搜尋時間。
Treap
Treap 被定義為隨機二叉搜尋樹 (BST)。在 Treap 中搜索類似於在任何其他 BST 中搜索元素。但是，Treap 具有以下屬性：距離為 d 的兩個元素之間的預期路徑長度表示為 O(log d)。因此，要從包含元素 b 的節點對元素 a 進行手指搜尋，可以從 b 元素向上遍歷樹，直到找到元素 a 的祖先，然後像往常一樣進行正常的 BST 搜尋。雖然計算節點是否是另一個節點的祖先並非易事，但可以增強樹以支援此類查詢，以提供預期的 O(log d) 手指搜尋時間。
繩子和樹
繩子（資料結構）的實現通常使用繩子位置迭代器來訪問字串。迭代器可以被認為是指向字串某個特定字元的手指。與大多數平衡樹一樣，繩子需要 O(log(m)) 時間才能在給定樹的根的情況下檢索樹中一個葉子中的資料。讀取樹的每個葉子似乎需要 O(m*log(m)) 時間。但是，透過儲存一些額外的資訊，可以實現迭代器以僅在 O(1) 時間內讀取“下一個”葉子，並在僅 O(m) 時間內讀取樹的每個葉子。
333 次瀏覽
